{-# LANGUAGE LambdaCase #-}
module Math.NumberTheory.Moduli.Cbrt
( CubicSymbol(..)
, cubicSymbol
, symbolToNum
) where
import Math.NumberTheory.Quadratic.EisensteinIntegers
import Math.NumberTheory.Utils.FromIntegral
import qualified Data.Euclidean as A
import Math.NumberTheory.Utils
import Data.Semigroup
data CubicSymbol = Zero | Omega | OmegaSquare | One deriving (CubicSymbol -> CubicSymbol -> Bool
(CubicSymbol -> CubicSymbol -> Bool)
-> (CubicSymbol -> CubicSymbol -> Bool) -> Eq CubicSymbol
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: CubicSymbol -> CubicSymbol -> Bool
$c/= :: CubicSymbol -> CubicSymbol -> Bool
== :: CubicSymbol -> CubicSymbol -> Bool
$c== :: CubicSymbol -> CubicSymbol -> Bool
Eq)
instance Semigroup CubicSymbol where
CubicSymbol
Zero <> :: CubicSymbol -> CubicSymbol -> CubicSymbol
<> CubicSymbol
_ = CubicSymbol
Zero
CubicSymbol
_ <> CubicSymbol
Zero = CubicSymbol
Zero
CubicSymbol
One <> CubicSymbol
y = CubicSymbol
y
CubicSymbol
x <> CubicSymbol
One = CubicSymbol
x
CubicSymbol
Omega <> CubicSymbol
Omega = CubicSymbol
OmegaSquare
CubicSymbol
Omega <> CubicSymbol
OmegaSquare = CubicSymbol
One
CubicSymbol
OmegaSquare <> CubicSymbol
Omega = CubicSymbol
One
CubicSymbol
OmegaSquare <> CubicSymbol
OmegaSquare = CubicSymbol
Omega
stimes :: b -> CubicSymbol -> CubicSymbol
stimes b
k CubicSymbol
n = case (b
k b -> b -> b
forall a. Integral a => a -> a -> a
`mod` b
3, CubicSymbol
n) of
(b
0, CubicSymbol
_) -> CubicSymbol
One
(b
1, CubicSymbol
symbol) -> CubicSymbol
symbol
(b
2, CubicSymbol
Omega) -> CubicSymbol
OmegaSquare
(b
2, CubicSymbol
OmegaSquare) -> CubicSymbol
Omega
(b
2, CubicSymbol
symbol) -> CubicSymbol
symbol
(b, CubicSymbol)
_ -> [Char] -> CubicSymbol
forall a. HasCallStack => [Char] -> a
error [Char]
"Math.NumberTheory.Moduli.Cbrt: exponentiation undefined."
instance Show CubicSymbol where
show :: CubicSymbol -> [Char]
show = \case
CubicSymbol
Zero -> [Char]
"0"
CubicSymbol
Omega -> [Char]
"ω"
CubicSymbol
OmegaSquare -> [Char]
"ω²"
CubicSymbol
One -> [Char]
"1"
symbolToNum :: CubicSymbol -> EisensteinInteger
symbolToNum :: CubicSymbol -> EisensteinInteger
symbolToNum = \case
CubicSymbol
Zero -> EisensteinInteger
0
CubicSymbol
Omega -> EisensteinInteger
ω
CubicSymbol
OmegaSquare -> -EisensteinInteger
1 EisensteinInteger -> EisensteinInteger -> EisensteinInteger
forall a. Num a => a -> a -> a
- EisensteinInteger
ω
CubicSymbol
One -> EisensteinInteger
1
cubicSymbol :: EisensteinInteger -> EisensteinInteger -> CubicSymbol
cubicSymbol :: EisensteinInteger -> EisensteinInteger -> CubicSymbol
cubicSymbol EisensteinInteger
alpha EisensteinInteger
beta = case EisensteinInteger
beta EisensteinInteger -> EisensteinInteger -> EisensteinInteger
forall a. Euclidean a => a -> a -> a
`A.rem` (EisensteinInteger
1 EisensteinInteger -> EisensteinInteger -> EisensteinInteger
forall a. Num a => a -> a -> a
- EisensteinInteger
ω) of
EisensteinInteger
0 -> [Char] -> CubicSymbol
forall a. HasCallStack => [Char] -> a
error [Char]
"Math.NumberTheory.Moduli.Cbrt: denominator is not coprime to 3."
EisensteinInteger
_ -> EisensteinInteger -> EisensteinInteger -> CubicSymbol
cubicSymbolHelper EisensteinInteger
alpha EisensteinInteger
beta
cubicSymbolHelper :: EisensteinInteger -> EisensteinInteger -> CubicSymbol
cubicSymbolHelper :: EisensteinInteger -> EisensteinInteger -> CubicSymbol
cubicSymbolHelper EisensteinInteger
alpha EisensteinInteger
beta = EisensteinInteger -> EisensteinInteger -> CubicSymbol
cubicReciprocity EisensteinInteger
primaryRemainder EisensteinInteger
primaryBeta CubicSymbol -> CubicSymbol -> CubicSymbol
forall a. Semigroup a => a -> a -> a
<> CubicSymbol
newSymbol
where
(EisensteinInteger
primaryRemainder, EisensteinInteger
primaryBeta, CubicSymbol
newSymbol) = EisensteinInteger
-> EisensteinInteger
-> (EisensteinInteger, EisensteinInteger, CubicSymbol)
extractPrimaryContributions EisensteinInteger
remainder EisensteinInteger
beta
remainder :: EisensteinInteger
remainder = EisensteinInteger -> EisensteinInteger -> EisensteinInteger
forall a. Euclidean a => a -> a -> a
A.rem EisensteinInteger
alpha EisensteinInteger
beta
cubicReciprocity :: EisensteinInteger -> EisensteinInteger -> CubicSymbol
cubicReciprocity :: EisensteinInteger -> EisensteinInteger -> CubicSymbol
cubicReciprocity EisensteinInteger
_ EisensteinInteger
1 = CubicSymbol
One
cubicReciprocity EisensteinInteger
0 EisensteinInteger
_ = CubicSymbol
Zero
cubicReciprocity EisensteinInteger
1 EisensteinInteger
_ = CubicSymbol
One
cubicReciprocity EisensteinInteger
alpha EisensteinInteger
beta = EisensteinInteger -> EisensteinInteger -> CubicSymbol
cubicSymbolHelper EisensteinInteger
beta EisensteinInteger
alpha
extractPrimaryContributions :: EisensteinInteger -> EisensteinInteger -> (EisensteinInteger, EisensteinInteger, CubicSymbol)
EisensteinInteger
alpha EisensteinInteger
beta = (EisensteinInteger
gamma, EisensteinInteger
delta, CubicSymbol
newSymbol)
where
newSymbol :: CubicSymbol
newSymbol = Integer -> CubicSymbol -> CubicSymbol
forall a b. (Semigroup a, Integral b) => b -> a -> a
stimes (Integer
j Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
m) CubicSymbol
Omega CubicSymbol -> CubicSymbol -> CubicSymbol
forall a. Semigroup a => a -> a -> a
<> Integer -> CubicSymbol -> CubicSymbol
forall a b. (Semigroup a, Integral b) => b -> a -> a
stimes (- Integer
m Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
n) CubicSymbol
i
Integer
m :+ Integer
n = EisensteinInteger -> EisensteinInteger -> EisensteinInteger
forall a. Euclidean a => a -> a -> a
A.quot (EisensteinInteger
delta EisensteinInteger -> EisensteinInteger -> EisensteinInteger
forall a. Num a => a -> a -> a
- EisensteinInteger
1) EisensteinInteger
3
(CubicSymbol
i, EisensteinInteger
gamma) = EisensteinInteger -> (CubicSymbol, EisensteinInteger)
getPrimaryDecomposition EisensteinInteger
alphaThreeFree
(CubicSymbol
_, EisensteinInteger
delta) = EisensteinInteger -> (CubicSymbol, EisensteinInteger)
getPrimaryDecomposition EisensteinInteger
beta
j :: Integer
j = Word -> Integer
wordToInteger Word
jIntWord
(Word
jIntWord, EisensteinInteger
alphaThreeFree) = EisensteinInteger -> EisensteinInteger -> (Word, EisensteinInteger)
forall a. (Eq a, GcdDomain a) => a -> a -> (Word, a)
splitOff (EisensteinInteger
1 EisensteinInteger -> EisensteinInteger -> EisensteinInteger
forall a. Num a => a -> a -> a
- EisensteinInteger
ω) EisensteinInteger
alpha
getPrimaryDecomposition :: EisensteinInteger -> (CubicSymbol, EisensteinInteger)
getPrimaryDecomposition :: EisensteinInteger -> (CubicSymbol, EisensteinInteger)
getPrimaryDecomposition EisensteinInteger
0 = (CubicSymbol
Zero, EisensteinInteger
0)
getPrimaryDecomposition EisensteinInteger
e = case EisensteinInteger
e EisensteinInteger -> EisensteinInteger -> EisensteinInteger
forall a. Euclidean a => a -> a -> a
`A.rem` EisensteinInteger
3 of
EisensteinInteger
1 -> (CubicSymbol
One, EisensteinInteger
e)
Integer
1 :+ Integer
1 -> (CubicSymbol
OmegaSquare, -EisensteinInteger
ω EisensteinInteger -> EisensteinInteger -> EisensteinInteger
forall a. Num a => a -> a -> a
* EisensteinInteger
e)
Integer
0 :+ Integer
1 -> (CubicSymbol
Omega, (-EisensteinInteger
1 EisensteinInteger -> EisensteinInteger -> EisensteinInteger
forall a. Num a => a -> a -> a
- EisensteinInteger
ω) EisensteinInteger -> EisensteinInteger -> EisensteinInteger
forall a. Num a => a -> a -> a
* EisensteinInteger
e)
(-1) :+ Integer
0 -> (CubicSymbol
One, -EisensteinInteger
e)
(-1) :+ (-1) -> (CubicSymbol
OmegaSquare, EisensteinInteger
ω EisensteinInteger -> EisensteinInteger -> EisensteinInteger
forall a. Num a => a -> a -> a
* EisensteinInteger
e)
Integer
0 :+ (-1) -> (CubicSymbol
Omega, (EisensteinInteger
1 EisensteinInteger -> EisensteinInteger -> EisensteinInteger
forall a. Num a => a -> a -> a
+ EisensteinInteger
ω) EisensteinInteger -> EisensteinInteger -> EisensteinInteger
forall a. Num a => a -> a -> a
* EisensteinInteger
e)
EisensteinInteger
_ -> [Char] -> (CubicSymbol, EisensteinInteger)
forall a. HasCallStack => [Char] -> a
error [Char]
"Math.NumberTheory.Moduli.Cbrt: primary decomposition failed."