{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE RankNTypes #-}
{-# LANGUAGE TypeFamilies #-}
module Math.NumberTheory.Quadratic.EisensteinIntegers
( EisensteinInteger(..)
, ω
, conjugate
, norm
, associates
, ids
, findPrime
, primes
) where
import Prelude hiding (quot, quotRem, gcd)
import Control.DeepSeq
import Data.Coerce
import Data.Euclidean
import Data.List (mapAccumL, partition)
import Data.Maybe
import Data.Ord (comparing)
import qualified Data.Semiring as S
import GHC.Generics (Generic)
import Math.NumberTheory.Moduli.Sqrt
import Math.NumberTheory.Primes.Types
import qualified Math.NumberTheory.Primes as U
import Math.NumberTheory.Utils (mergeBy)
import Math.NumberTheory.Utils.FromIntegral
infix 6 :+
data EisensteinInteger = !Integer :+ !Integer
deriving (EisensteinInteger -> EisensteinInteger -> Bool
(EisensteinInteger -> EisensteinInteger -> Bool)
-> (EisensteinInteger -> EisensteinInteger -> Bool)
-> Eq EisensteinInteger
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: EisensteinInteger -> EisensteinInteger -> Bool
$c/= :: EisensteinInteger -> EisensteinInteger -> Bool
== :: EisensteinInteger -> EisensteinInteger -> Bool
$c== :: EisensteinInteger -> EisensteinInteger -> Bool
Eq, Eq EisensteinInteger
Eq EisensteinInteger
-> (EisensteinInteger -> EisensteinInteger -> Ordering)
-> (EisensteinInteger -> EisensteinInteger -> Bool)
-> (EisensteinInteger -> EisensteinInteger -> Bool)
-> (EisensteinInteger -> EisensteinInteger -> Bool)
-> (EisensteinInteger -> EisensteinInteger -> Bool)
-> (EisensteinInteger -> EisensteinInteger -> EisensteinInteger)
-> (EisensteinInteger -> EisensteinInteger -> EisensteinInteger)
-> Ord EisensteinInteger
EisensteinInteger -> EisensteinInteger -> Bool
EisensteinInteger -> EisensteinInteger -> Ordering
EisensteinInteger -> EisensteinInteger -> EisensteinInteger
forall a.
Eq a
-> (a -> a -> Ordering)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> Bool)
-> (a -> a -> a)
-> (a -> a -> a)
-> Ord a
min :: EisensteinInteger -> EisensteinInteger -> EisensteinInteger
$cmin :: EisensteinInteger -> EisensteinInteger -> EisensteinInteger
max :: EisensteinInteger -> EisensteinInteger -> EisensteinInteger
$cmax :: EisensteinInteger -> EisensteinInteger -> EisensteinInteger
>= :: EisensteinInteger -> EisensteinInteger -> Bool
$c>= :: EisensteinInteger -> EisensteinInteger -> Bool
> :: EisensteinInteger -> EisensteinInteger -> Bool
$c> :: EisensteinInteger -> EisensteinInteger -> Bool
<= :: EisensteinInteger -> EisensteinInteger -> Bool
$c<= :: EisensteinInteger -> EisensteinInteger -> Bool
< :: EisensteinInteger -> EisensteinInteger -> Bool
$c< :: EisensteinInteger -> EisensteinInteger -> Bool
compare :: EisensteinInteger -> EisensteinInteger -> Ordering
$ccompare :: EisensteinInteger -> EisensteinInteger -> Ordering
$cp1Ord :: Eq EisensteinInteger
Ord, (forall x. EisensteinInteger -> Rep EisensteinInteger x)
-> (forall x. Rep EisensteinInteger x -> EisensteinInteger)
-> Generic EisensteinInteger
forall x. Rep EisensteinInteger x -> EisensteinInteger
forall x. EisensteinInteger -> Rep EisensteinInteger x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
$cto :: forall x. Rep EisensteinInteger x -> EisensteinInteger
$cfrom :: forall x. EisensteinInteger -> Rep EisensteinInteger x
Generic)
instance NFData EisensteinInteger
ω :: EisensteinInteger
ω :: EisensteinInteger
ω = Integer
0 Integer -> Integer -> EisensteinInteger
:+ Integer
1
instance Show EisensteinInteger where
show :: EisensteinInteger -> String
show (Integer
a :+ Integer
b)
| Integer
b Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0 = Integer -> String
forall a. Show a => a -> String
show Integer
a
| Integer
a Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0 = String
s String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
b'
| Bool
otherwise = Integer -> String
forall a. Show a => a -> String
show Integer
a String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
op String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
b'
where
b' :: String
b' = if Integer -> Integer
forall a. Num a => a -> a
abs Integer
b Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 then String
"ω" else Integer -> String
forall a. Show a => a -> String
show (Integer -> Integer
forall a. Num a => a -> a
abs Integer
b) String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
"*ω"
op :: String
op = if Integer
b Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
> Integer
0 then String
"+" else String
"-"
s :: String
s = if Integer
b Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
> Integer
0 then String
"" else String
"-"
instance Num EisensteinInteger where
+ :: EisensteinInteger -> EisensteinInteger -> EisensteinInteger
(+) (Integer
a :+ Integer
b) (Integer
c :+ Integer
d) = (Integer
a Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
c) Integer -> Integer -> EisensteinInteger
:+ (Integer
b Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
d)
* :: EisensteinInteger -> EisensteinInteger -> EisensteinInteger
(*) (Integer
a :+ Integer
b) (Integer
c :+ Integer
d) = (Integer
a Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
c Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
b Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
d) Integer -> Integer -> EisensteinInteger
:+ (Integer
b Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* (Integer
c Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
d) Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
a Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
d)
abs :: EisensteinInteger -> EisensteinInteger
abs = (EisensteinInteger, EisensteinInteger) -> EisensteinInteger
forall a b. (a, b) -> a
fst ((EisensteinInteger, EisensteinInteger) -> EisensteinInteger)
-> (EisensteinInteger -> (EisensteinInteger, EisensteinInteger))
-> EisensteinInteger
-> EisensteinInteger
forall b c a. (b -> c) -> (a -> b) -> a -> c
. EisensteinInteger -> (EisensteinInteger, EisensteinInteger)
absSignum
negate :: EisensteinInteger -> EisensteinInteger
negate (Integer
a :+ Integer
b) = (-Integer
a) Integer -> Integer -> EisensteinInteger
:+ (-Integer
b)
fromInteger :: Integer -> EisensteinInteger
fromInteger Integer
n = Integer
n Integer -> Integer -> EisensteinInteger
:+ Integer
0
signum :: EisensteinInteger -> EisensteinInteger
signum = (EisensteinInteger, EisensteinInteger) -> EisensteinInteger
forall a b. (a, b) -> b
snd ((EisensteinInteger, EisensteinInteger) -> EisensteinInteger)
-> (EisensteinInteger -> (EisensteinInteger, EisensteinInteger))
-> EisensteinInteger
-> EisensteinInteger
forall b c a. (b -> c) -> (a -> b) -> a -> c
. EisensteinInteger -> (EisensteinInteger, EisensteinInteger)
absSignum
instance S.Semiring EisensteinInteger where
plus :: EisensteinInteger -> EisensteinInteger -> EisensteinInteger
plus = EisensteinInteger -> EisensteinInteger -> EisensteinInteger
forall a. Num a => a -> a -> a
(+)
times :: EisensteinInteger -> EisensteinInteger -> EisensteinInteger
times = EisensteinInteger -> EisensteinInteger -> EisensteinInteger
forall a. Num a => a -> a -> a
(*)
zero :: EisensteinInteger
zero = Integer
0 Integer -> Integer -> EisensteinInteger
:+ Integer
0
one :: EisensteinInteger
one = Integer
1 Integer -> Integer -> EisensteinInteger
:+ Integer
0
fromNatural :: Natural -> EisensteinInteger
fromNatural Natural
n = Natural -> Integer
naturalToInteger Natural
n Integer -> Integer -> EisensteinInteger
:+ Integer
0
instance S.Ring EisensteinInteger where
negate :: EisensteinInteger -> EisensteinInteger
negate = EisensteinInteger -> EisensteinInteger
forall a. Num a => a -> a
negate
absSignum :: EisensteinInteger -> (EisensteinInteger, EisensteinInteger)
absSignum :: EisensteinInteger -> (EisensteinInteger, EisensteinInteger)
absSignum EisensteinInteger
0 = (EisensteinInteger
0, EisensteinInteger
0)
absSignum z :: EisensteinInteger
z@(Integer
a :+ Integer
b)
| Integer
a Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
> Integer
b Bool -> Bool -> Bool
&& Integer
b Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
>= Integer
0 = (EisensteinInteger
z, EisensteinInteger
1)
| Integer
b Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
>= Integer
a Bool -> Bool -> Bool
&& Integer
a Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
> Integer
0 = (Integer
b Integer -> Integer -> EisensteinInteger
:+ (Integer
b Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
a), Integer
1 Integer -> Integer -> EisensteinInteger
:+ Integer
1)
| Integer
b Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
> Integer
0 Bool -> Bool -> Bool
&& Integer
0 Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
>= Integer
a = ((Integer
b Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
a) Integer -> Integer -> EisensteinInteger
:+ (-Integer
a), Integer
0 Integer -> Integer -> EisensteinInteger
:+ Integer
1)
| Integer
a Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
b Bool -> Bool -> Bool
&& Integer
b Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
<= Integer
0 = (-EisensteinInteger
z, -EisensteinInteger
1)
| Integer
b Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
<= Integer
a Bool -> Bool -> Bool
&& Integer
a Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
0 = ((-Integer
b) Integer -> Integer -> EisensteinInteger
:+ (Integer
a Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
b), (-Integer
1) Integer -> Integer -> EisensteinInteger
:+ (-Integer
1))
| Bool
otherwise = ((Integer
a Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
b) Integer -> Integer -> EisensteinInteger
:+ Integer
a, Integer
0 Integer -> Integer -> EisensteinInteger
:+ (-Integer
1))
ids :: [EisensteinInteger]
ids :: [EisensteinInteger]
ids = Int -> [EisensteinInteger] -> [EisensteinInteger]
forall a. Int -> [a] -> [a]
take Int
6 ((EisensteinInteger -> EisensteinInteger)
-> EisensteinInteger -> [EisensteinInteger]
forall a. (a -> a) -> a -> [a]
iterate ((EisensteinInteger
1 EisensteinInteger -> EisensteinInteger -> EisensteinInteger
forall a. Num a => a -> a -> a
+ EisensteinInteger
ω) EisensteinInteger -> EisensteinInteger -> EisensteinInteger
forall a. Num a => a -> a -> a
*) EisensteinInteger
1)
associates :: EisensteinInteger -> [EisensteinInteger]
associates :: EisensteinInteger -> [EisensteinInteger]
associates EisensteinInteger
e = (EisensteinInteger -> EisensteinInteger)
-> [EisensteinInteger] -> [EisensteinInteger]
forall a b. (a -> b) -> [a] -> [b]
map (EisensteinInteger
e EisensteinInteger -> EisensteinInteger -> EisensteinInteger
forall a. Num a => a -> a -> a
*) [EisensteinInteger]
ids
instance GcdDomain EisensteinInteger
instance Euclidean EisensteinInteger where
degree :: EisensteinInteger -> Natural
degree = Integer -> Natural
forall a. Num a => Integer -> a
fromInteger (Integer -> Natural)
-> (EisensteinInteger -> Integer) -> EisensteinInteger -> Natural
forall b c a. (b -> c) -> (a -> b) -> a -> c
. EisensteinInteger -> Integer
norm
quotRem :: EisensteinInteger
-> EisensteinInteger -> (EisensteinInteger, EisensteinInteger)
quotRem EisensteinInteger
x (Integer
d :+ Integer
0) = EisensteinInteger
-> Integer -> (EisensteinInteger, EisensteinInteger)
quotRemInt EisensteinInteger
x Integer
d
quotRem EisensteinInteger
x EisensteinInteger
y = (EisensteinInteger
q, EisensteinInteger
x EisensteinInteger -> EisensteinInteger -> EisensteinInteger
forall a. Num a => a -> a -> a
- EisensteinInteger
q EisensteinInteger -> EisensteinInteger -> EisensteinInteger
forall a. Num a => a -> a -> a
* EisensteinInteger
y)
where
(EisensteinInteger
q, EisensteinInteger
_) = EisensteinInteger
-> Integer -> (EisensteinInteger, EisensteinInteger)
quotRemInt (EisensteinInteger
x EisensteinInteger -> EisensteinInteger -> EisensteinInteger
forall a. Num a => a -> a -> a
* EisensteinInteger -> EisensteinInteger
conjugate EisensteinInteger
y) (EisensteinInteger -> Integer
norm EisensteinInteger
y)
quotRemInt :: EisensteinInteger -> Integer -> (EisensteinInteger, EisensteinInteger)
quotRemInt :: EisensteinInteger
-> Integer -> (EisensteinInteger, EisensteinInteger)
quotRemInt EisensteinInteger
z Integer
1 = ( EisensteinInteger
z, EisensteinInteger
0)
quotRemInt EisensteinInteger
z (-1) = (-EisensteinInteger
z, EisensteinInteger
0)
quotRemInt (Integer
a :+ Integer
b) Integer
c = (Integer
qa Integer -> Integer -> EisensteinInteger
:+ Integer
qb, (Integer
ra Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
bumpA) Integer -> Integer -> EisensteinInteger
:+ (Integer
rb Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
bumpB))
where
halfC :: Integer
halfC = Integer -> Integer
forall a. Num a => a -> a
abs Integer
c Integer -> Integer -> Integer
forall a. Euclidean a => a -> a -> a
`quot` Integer
2
bumpA :: Integer
bumpA = Integer -> Integer
forall a. Num a => a -> a
signum Integer
a Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
halfC
bumpB :: Integer
bumpB = Integer -> Integer
forall a. Num a => a -> a
signum Integer
b Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
halfC
(Integer
qa, Integer
ra) = (Integer
a Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
bumpA) Integer -> Integer -> (Integer, Integer)
forall a. Euclidean a => a -> a -> (a, a)
`quotRem` Integer
c
(Integer
qb, Integer
rb) = (Integer
b Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
bumpB) Integer -> Integer -> (Integer, Integer)
forall a. Euclidean a => a -> a -> (a, a)
`quotRem` Integer
c
conjugate :: EisensteinInteger -> EisensteinInteger
conjugate :: EisensteinInteger -> EisensteinInteger
conjugate (Integer
a :+ Integer
b) = (Integer
a Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
b) Integer -> Integer -> EisensteinInteger
:+ (-Integer
b)
norm :: EisensteinInteger -> Integer
norm :: EisensteinInteger -> Integer
norm (Integer
a :+ Integer
b) = Integer
aInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
a Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
a Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
b Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
bInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
b
isPrime :: EisensteinInteger -> Bool
isPrime :: EisensteinInteger -> Bool
isPrime EisensteinInteger
e | EisensteinInteger
e EisensteinInteger -> EisensteinInteger -> Bool
forall a. Eq a => a -> a -> Bool
== EisensteinInteger
0 = Bool
False
| Integer
a' Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
2 Bool -> Bool -> Bool
&& Integer
b' Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 = Bool
True
| Integer
b' Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0 Bool -> Bool -> Bool
&& Integer
a' Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
3 Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
2 = Maybe (Prime Integer) -> Bool
forall a. Maybe a -> Bool
isJust (Maybe (Prime Integer) -> Bool) -> Maybe (Prime Integer) -> Bool
forall a b. (a -> b) -> a -> b
$ Integer -> Maybe (Prime Integer)
forall a. UniqueFactorisation a => a -> Maybe (Prime a)
U.isPrime Integer
a'
| Integer
nE Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
3 Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 = Maybe (Prime Integer) -> Bool
forall a. Maybe a -> Bool
isJust (Maybe (Prime Integer) -> Bool) -> Maybe (Prime Integer) -> Bool
forall a b. (a -> b) -> a -> b
$ Integer -> Maybe (Prime Integer)
forall a. UniqueFactorisation a => a -> Maybe (Prime a)
U.isPrime Integer
nE
| Bool
otherwise = Bool
False
where nE :: Integer
nE = EisensteinInteger -> Integer
norm EisensteinInteger
e
Integer
a' :+ Integer
b' = EisensteinInteger -> EisensteinInteger
forall a. Num a => a -> a
abs EisensteinInteger
e
divideByThree :: EisensteinInteger -> (Word, EisensteinInteger)
divideByThree :: EisensteinInteger -> (Word, EisensteinInteger)
divideByThree = Word -> EisensteinInteger -> (Word, EisensteinInteger)
go Word
0
where
go :: Word -> EisensteinInteger -> (Word, EisensteinInteger)
go :: Word -> EisensteinInteger -> (Word, EisensteinInteger)
go !Word
n z :: EisensteinInteger
z@(Integer
a :+ Integer
b) | Integer
r1 Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0 Bool -> Bool -> Bool
&& Integer
r2 Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0 = Word -> EisensteinInteger -> (Word, EisensteinInteger)
go (Word
n Word -> Word -> Word
forall a. Num a => a -> a -> a
+ Word
1) (Integer
q1 Integer -> Integer -> EisensteinInteger
:+ Integer
q2)
| Bool
otherwise = (Word
n, EisensteinInteger -> EisensteinInteger
forall a. Num a => a -> a
abs EisensteinInteger
z)
where
(Integer
q1, Integer
r1) = Integer -> Integer -> (Integer, Integer)
forall a. Integral a => a -> a -> (a, a)
divMod (Integer
a Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
a Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
b) Integer
3
(Integer
q2, Integer
r2) = Integer -> Integer -> (Integer, Integer)
forall a. Integral a => a -> a -> (a, a)
divMod (Integer
a Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
b) Integer
3
findPrime :: Prime Integer -> U.Prime EisensteinInteger
findPrime :: Prime Integer -> Prime EisensteinInteger
findPrime Prime Integer
p = case (Integer
r, Integer -> Prime Integer -> [Integer]
sqrtsModPrime (Integer
9 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
q Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
q Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
1) Prime Integer
p) of
(Integer
1, Integer
z : [Integer]
_) -> EisensteinInteger -> Prime EisensteinInteger
forall a. a -> Prime a
Prime (EisensteinInteger -> Prime EisensteinInteger)
-> EisensteinInteger -> Prime EisensteinInteger
forall a b. (a -> b) -> a -> b
$ EisensteinInteger -> EisensteinInteger
forall a. Num a => a -> a
abs (EisensteinInteger -> EisensteinInteger)
-> EisensteinInteger -> EisensteinInteger
forall a b. (a -> b) -> a -> b
$ EisensteinInteger -> EisensteinInteger -> EisensteinInteger
forall a. GcdDomain a => a -> a -> a
gcd (Prime Integer -> Integer
forall a. Prime a -> a
unPrime Prime Integer
p Integer -> Integer -> EisensteinInteger
:+ Integer
0) ((Integer
z Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
3 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
q) Integer -> Integer -> EisensteinInteger
:+ Integer
1)
(Integer, [Integer])
_ -> String -> Prime EisensteinInteger
forall a. HasCallStack => String -> a
error String
"findPrime: argument must be prime p = 6k + 1"
where
(Integer
q, Integer
r) = Prime Integer -> Integer
forall a. Prime a -> a
unPrime Prime Integer
p Integer -> Integer -> (Integer, Integer)
forall a. Euclidean a => a -> a -> (a, a)
`quotRem` Integer
6
primes :: [Prime EisensteinInteger]
primes :: [Prime EisensteinInteger]
primes = [EisensteinInteger] -> [Prime EisensteinInteger]
coerce ([EisensteinInteger] -> [Prime EisensteinInteger])
-> [EisensteinInteger] -> [Prime EisensteinInteger]
forall a b. (a -> b) -> a -> b
$ (Integer
2 Integer -> Integer -> EisensteinInteger
:+ Integer
1) EisensteinInteger -> [EisensteinInteger] -> [EisensteinInteger]
forall a. a -> [a] -> [a]
: (EisensteinInteger -> EisensteinInteger -> Ordering)
-> [EisensteinInteger]
-> [EisensteinInteger]
-> [EisensteinInteger]
forall a. (a -> a -> Ordering) -> [a] -> [a] -> [a]
mergeBy ((EisensteinInteger -> Integer)
-> EisensteinInteger -> EisensteinInteger -> Ordering
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing EisensteinInteger -> Integer
norm) [EisensteinInteger]
l [EisensteinInteger]
r
where
leftPrimes, rightPrimes :: [Prime Integer]
([Prime Integer]
leftPrimes, [Prime Integer]
rightPrimes) = (Prime Integer -> Bool)
-> [Prime Integer] -> ([Prime Integer], [Prime Integer])
forall a. (a -> Bool) -> [a] -> ([a], [a])
partition (\Prime Integer
p -> Prime Integer -> Integer
forall a. Prime a -> a
unPrime Prime Integer
p Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
3 Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
2) [Integer -> Prime Integer
forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
a -> Prime a
U.nextPrime Integer
2 ..]
rightPrimes' :: [Prime Integer]
rightPrimes' = (Prime Integer -> Bool) -> [Prime Integer] -> [Prime Integer]
forall a. (a -> Bool) -> [a] -> [a]
filter (\Prime Integer
prime -> Prime Integer -> Integer
forall a. Prime a -> a
unPrime Prime Integer
prime Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
3 Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1) ([Prime Integer] -> [Prime Integer])
-> [Prime Integer] -> [Prime Integer]
forall a b. (a -> b) -> a -> b
$ [Prime Integer] -> [Prime Integer]
forall a. [a] -> [a]
tail [Prime Integer]
rightPrimes
l :: [EisensteinInteger]
l = [Prime Integer -> Integer
forall a. Prime a -> a
unPrime Prime Integer
p Integer -> Integer -> EisensteinInteger
:+ Integer
0 | Prime Integer
p <- [Prime Integer]
leftPrimes]
r :: [EisensteinInteger]
r = [EisensteinInteger
g | Prime Integer
p <- [Prime Integer]
rightPrimes', let Integer
x :+ Integer
y = Prime EisensteinInteger -> EisensteinInteger
forall a. Prime a -> a
unPrime (Prime Integer -> Prime EisensteinInteger
findPrime Prime Integer
p), EisensteinInteger
g <- [Integer
x Integer -> Integer -> EisensteinInteger
:+ Integer
y, Integer
x Integer -> Integer -> EisensteinInteger
:+ (Integer
x Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
y)]]
factorise :: EisensteinInteger -> [(Prime EisensteinInteger, Word)]
factorise :: EisensteinInteger -> [(Prime EisensteinInteger, Word)]
factorise EisensteinInteger
g = [[(Prime EisensteinInteger, Word)]]
-> [(Prime EisensteinInteger, Word)]
forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat ([[(Prime EisensteinInteger, Word)]]
-> [(Prime EisensteinInteger, Word)])
-> [[(Prime EisensteinInteger, Word)]]
-> [(Prime EisensteinInteger, Word)]
forall a b. (a -> b) -> a -> b
$
(EisensteinInteger, [[(Prime EisensteinInteger, Word)]])
-> [[(Prime EisensteinInteger, Word)]]
forall a b. (a, b) -> b
snd ((EisensteinInteger, [[(Prime EisensteinInteger, Word)]])
-> [[(Prime EisensteinInteger, Word)]])
-> (EisensteinInteger, [[(Prime EisensteinInteger, Word)]])
-> [[(Prime EisensteinInteger, Word)]]
forall a b. (a -> b) -> a -> b
$
(EisensteinInteger
-> (Prime Integer, Word)
-> (EisensteinInteger, [(Prime EisensteinInteger, Word)]))
-> EisensteinInteger
-> [(Prime Integer, Word)]
-> (EisensteinInteger, [[(Prime EisensteinInteger, Word)]])
forall (t :: * -> *) a b c.
Traversable t =>
(a -> b -> (a, c)) -> a -> t b -> (a, t c)
mapAccumL EisensteinInteger
-> (Prime Integer, Word)
-> (EisensteinInteger, [(Prime EisensteinInteger, Word)])
go (EisensteinInteger -> EisensteinInteger
forall a. Num a => a -> a
abs EisensteinInteger
g) (Integer -> [(Prime Integer, Word)]
forall a. UniqueFactorisation a => a -> [(Prime a, Word)]
U.factorise (Integer -> [(Prime Integer, Word)])
-> Integer -> [(Prime Integer, Word)]
forall a b. (a -> b) -> a -> b
$ EisensteinInteger -> Integer
norm EisensteinInteger
g)
where
go :: EisensteinInteger -> (Prime Integer, Word) -> (EisensteinInteger, [(Prime EisensteinInteger, Word)])
go :: EisensteinInteger
-> (Prime Integer, Word)
-> (EisensteinInteger, [(Prime EisensteinInteger, Word)])
go EisensteinInteger
z (Prime Integer
3, Word
e)
| Word
e Word -> Word -> Bool
forall a. Eq a => a -> a -> Bool
== Word
n = (EisensteinInteger
q, [(EisensteinInteger -> Prime EisensteinInteger
forall a. a -> Prime a
Prime (Integer
2 Integer -> Integer -> EisensteinInteger
:+ Integer
1), Word
e)])
| Bool
otherwise = String -> (EisensteinInteger, [(Prime EisensteinInteger, Word)])
forall a. HasCallStack => String -> a
error (String -> (EisensteinInteger, [(Prime EisensteinInteger, Word)]))
-> String -> (EisensteinInteger, [(Prime EisensteinInteger, Word)])
forall a b. (a -> b) -> a -> b
$ String
"3 is a prime factor of the norm of z = " String -> ShowS
forall a. [a] -> [a] -> [a]
++ EisensteinInteger -> String
forall a. Show a => a -> String
show EisensteinInteger
z
String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" with multiplicity " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Word -> String
forall a. Show a => a -> String
show Word
e
String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" but (1 - ω) only divides z " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Word -> String
forall a. Show a => a -> String
show Word
n String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
"times."
where
(Word
n, EisensteinInteger
q) = EisensteinInteger -> (Word, EisensteinInteger)
divideByThree EisensteinInteger
z
go EisensteinInteger
z (Prime Integer
p, Word
e)
| Prime Integer -> Integer
forall a. Prime a -> a
unPrime Prime Integer
p Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`mod` Integer
3 Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
2
= let e' :: Word
e' = Word
e Word -> Word -> Word
forall a. Euclidean a => a -> a -> a
`quot` Word
2 in (EisensteinInteger
z EisensteinInteger -> Integer -> EisensteinInteger
`quotI` (Prime Integer -> Integer
forall a. Prime a -> a
unPrime Prime Integer
p Integer -> Word -> Integer
forall a b. (Num a, Integral b) => a -> b -> a
^ Word
e'), [(EisensteinInteger -> Prime EisensteinInteger
forall a. a -> Prime a
Prime (Prime Integer -> Integer
forall a. Prime a -> a
unPrime Prime Integer
p Integer -> Integer -> EisensteinInteger
:+ Integer
0), Word
e')])
| Bool
otherwise = (EisensteinInteger
z', ((Prime EisensteinInteger, Word) -> Bool)
-> [(Prime EisensteinInteger, Word)]
-> [(Prime EisensteinInteger, Word)]
forall a. (a -> Bool) -> [a] -> [a]
filter ((Word -> Word -> Bool
forall a. Ord a => a -> a -> Bool
> Word
0) (Word -> Bool)
-> ((Prime EisensteinInteger, Word) -> Word)
-> (Prime EisensteinInteger, Word)
-> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Prime EisensteinInteger, Word) -> Word
forall a b. (a, b) -> b
snd) [(Prime EisensteinInteger
gp, Word
k), (Prime EisensteinInteger
gp', Word
k')])
where
gp :: Prime EisensteinInteger
gp = Prime Integer -> Prime EisensteinInteger
findPrime Prime Integer
p
Integer
x :+ Integer
y = Prime EisensteinInteger -> EisensteinInteger
forall a. Prime a -> a
unPrime Prime EisensteinInteger
gp
gp' :: Prime EisensteinInteger
gp' = EisensteinInteger -> Prime EisensteinInteger
forall a. a -> Prime a
Prime (Integer
x Integer -> Integer -> EisensteinInteger
:+ (Integer
x Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer
y))
(Word
k, Word
k', EisensteinInteger
z') = Prime EisensteinInteger
-> Prime EisensteinInteger
-> Integer
-> Word
-> EisensteinInteger
-> (Word, Word, EisensteinInteger)
divideByPrime Prime EisensteinInteger
gp Prime EisensteinInteger
gp' (Prime Integer -> Integer
forall a. Prime a -> a
unPrime Prime Integer
p) Word
e EisensteinInteger
z
quotI :: EisensteinInteger -> Integer -> EisensteinInteger
quotI (Integer
a :+ Integer
b) Integer
n = Integer
a Integer -> Integer -> Integer
forall a. Euclidean a => a -> a -> a
`quot` Integer
n Integer -> Integer -> EisensteinInteger
:+ Integer
b Integer -> Integer -> Integer
forall a. Euclidean a => a -> a -> a
`quot` Integer
n
divideByPrime
:: Prime EisensteinInteger
-> Prime EisensteinInteger
-> Integer
-> Word
-> EisensteinInteger
-> ( Word
, Word
, EisensteinInteger
)
divideByPrime :: Prime EisensteinInteger
-> Prime EisensteinInteger
-> Integer
-> Word
-> EisensteinInteger
-> (Word, Word, EisensteinInteger)
divideByPrime Prime EisensteinInteger
p Prime EisensteinInteger
p' Integer
np Word
k = Word
-> Word -> EisensteinInteger -> (Word, Word, EisensteinInteger)
go Word
k Word
0
where
go :: Word -> Word -> EisensteinInteger -> (Word, Word, EisensteinInteger)
go :: Word
-> Word -> EisensteinInteger -> (Word, Word, EisensteinInteger)
go Word
0 Word
d EisensteinInteger
z = (Word
d, Word
d, EisensteinInteger
z)
go Word
c Word
d EisensteinInteger
z | Word
c Word -> Word -> Bool
forall a. Ord a => a -> a -> Bool
>= Word
2, Just EisensteinInteger
z' <- EisensteinInteger
z EisensteinInteger -> Integer -> Maybe EisensteinInteger
`quotEvenI` Integer
np = Word
-> Word -> EisensteinInteger -> (Word, Word, EisensteinInteger)
go (Word
c Word -> Word -> Word
forall a. Num a => a -> a -> a
- Word
2) (Word
d Word -> Word -> Word
forall a. Num a => a -> a -> a
+ Word
1) EisensteinInteger
z'
go Word
c Word
d EisensteinInteger
z = (Word
d Word -> Word -> Word
forall a. Num a => a -> a -> a
+ Word
d1, Word
d Word -> Word -> Word
forall a. Num a => a -> a -> a
+ Word
d2, EisensteinInteger
z'')
where
(Word
d1, EisensteinInteger
z') = Word -> Word -> EisensteinInteger -> (Word, EisensteinInteger)
go1 Word
c Word
0 EisensteinInteger
z
d2 :: Word
d2 = Word
c Word -> Word -> Word
forall a. Num a => a -> a -> a
- Word
d1
z'' :: EisensteinInteger
z'' = (EisensteinInteger -> EisensteinInteger)
-> EisensteinInteger -> [EisensteinInteger]
forall a. (a -> a) -> a -> [a]
iterate (\EisensteinInteger
g -> EisensteinInteger -> Maybe EisensteinInteger -> EisensteinInteger
forall a. a -> Maybe a -> a
fromMaybe EisensteinInteger
err (Maybe EisensteinInteger -> EisensteinInteger)
-> Maybe EisensteinInteger -> EisensteinInteger
forall a b. (a -> b) -> a -> b
$ (EisensteinInteger
g EisensteinInteger -> EisensteinInteger -> EisensteinInteger
forall a. Num a => a -> a -> a
* Prime EisensteinInteger -> EisensteinInteger
forall a. Prime a -> a
unPrime Prime EisensteinInteger
p) EisensteinInteger -> Integer -> Maybe EisensteinInteger
`quotEvenI` Integer
np) EisensteinInteger
z' [EisensteinInteger] -> Int -> EisensteinInteger
forall a. [a] -> Int -> a
!! Int -> Int -> Int
forall a. Ord a => a -> a -> a
max Int
0 (Word -> Int
wordToInt Word
d2)
go1 :: Word -> Word -> EisensteinInteger -> (Word, EisensteinInteger)
go1 :: Word -> Word -> EisensteinInteger -> (Word, EisensteinInteger)
go1 Word
0 Word
d EisensteinInteger
z = (Word
d, EisensteinInteger
z)
go1 Word
c Word
d EisensteinInteger
z
| Just EisensteinInteger
z' <- (EisensteinInteger
z EisensteinInteger -> EisensteinInteger -> EisensteinInteger
forall a. Num a => a -> a -> a
* Prime EisensteinInteger -> EisensteinInteger
forall a. Prime a -> a
unPrime Prime EisensteinInteger
p') EisensteinInteger -> Integer -> Maybe EisensteinInteger
`quotEvenI` Integer
np
= Word -> Word -> EisensteinInteger -> (Word, EisensteinInteger)
go1 (Word
c Word -> Word -> Word
forall a. Num a => a -> a -> a
- Word
1) (Word
d Word -> Word -> Word
forall a. Num a => a -> a -> a
+ Word
1) EisensteinInteger
z'
| Bool
otherwise
= (Word
d, EisensteinInteger
z)
err :: EisensteinInteger
err = String -> EisensteinInteger
forall a. HasCallStack => String -> a
error (String -> EisensteinInteger) -> String -> EisensteinInteger
forall a b. (a -> b) -> a -> b
$ String
"divideByPrime: malformed arguments" String -> ShowS
forall a. [a] -> [a] -> [a]
++ (Prime EisensteinInteger, Integer, Word) -> String
forall a. Show a => a -> String
show (Prime EisensteinInteger
p, Integer
np, Word
k)
quotEvenI :: EisensteinInteger -> Integer -> Maybe EisensteinInteger
quotEvenI :: EisensteinInteger -> Integer -> Maybe EisensteinInteger
quotEvenI (Integer
x :+ Integer
y) Integer
n
| Integer
xr Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0 , Integer
yr Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0 = EisensteinInteger -> Maybe EisensteinInteger
forall a. a -> Maybe a
Just (Integer
xq Integer -> Integer -> EisensteinInteger
:+ Integer
yq)
| Bool
otherwise = Maybe EisensteinInteger
forall a. Maybe a
Nothing
where
(Integer
xq, Integer
xr) = Integer
x Integer -> Integer -> (Integer, Integer)
forall a. Euclidean a => a -> a -> (a, a)
`quotRem` Integer
n
(Integer
yq, Integer
yr) = Integer
y Integer -> Integer -> (Integer, Integer)
forall a. Euclidean a => a -> a -> (a, a)
`quotRem` Integer
n
instance U.UniqueFactorisation EisensteinInteger where
factorise :: EisensteinInteger -> [(Prime EisensteinInteger, Word)]
factorise EisensteinInteger
0 = []
factorise EisensteinInteger
e = [(Prime EisensteinInteger, Word)]
-> [(Prime EisensteinInteger, Word)]
coerce ([(Prime EisensteinInteger, Word)]
-> [(Prime EisensteinInteger, Word)])
-> [(Prime EisensteinInteger, Word)]
-> [(Prime EisensteinInteger, Word)]
forall a b. (a -> b) -> a -> b
$ EisensteinInteger -> [(Prime EisensteinInteger, Word)]
factorise EisensteinInteger
e
isPrime :: EisensteinInteger -> Maybe (Prime EisensteinInteger)
isPrime EisensteinInteger
e = if EisensteinInteger -> Bool
isPrime EisensteinInteger
e then Prime EisensteinInteger -> Maybe (Prime EisensteinInteger)
forall a. a -> Maybe a
Just (EisensteinInteger -> Prime EisensteinInteger
forall a. a -> Prime a
Prime EisensteinInteger
e) else Maybe (Prime EisensteinInteger)
forall a. Maybe a
Nothing