{-# LANGUAGE BangPatterns #-}
{-# LANGUAGE DeriveGeneric #-}
{-# LANGUAGE PostfixOperators #-}
{-# 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)
import Data.List.Infinite (Infinite(..), (...))
import qualified Data.List.Infinite as Inf
import Data.List.NonEmpty (NonEmpty(..))
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
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
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
Ord, 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 forall a. Eq a => a -> a -> Bool
== Integer
0 = forall a. Show a => a -> String
show Integer
a
| Integer
a forall a. Eq a => a -> a -> Bool
== Integer
0 = String
s forall a. [a] -> [a] -> [a]
++ String
b'
| Bool
otherwise = forall a. Show a => a -> String
show Integer
a forall a. [a] -> [a] -> [a]
++ String
op forall a. [a] -> [a] -> [a]
++ String
b'
where
b' :: String
b' = if forall a. Num a => a -> a
abs Integer
b forall a. Eq a => a -> a -> Bool
== Integer
1 then String
"ω" else forall a. Show a => a -> String
show (forall a. Num a => a -> a
abs Integer
b) forall a. [a] -> [a] -> [a]
++ String
"*ω"
op :: String
op = if Integer
b forall a. Ord a => a -> a -> Bool
> Integer
0 then String
"+" else String
"-"
s :: String
s = if Integer
b 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 forall a. Num a => a -> a -> a
+ Integer
c) Integer -> Integer -> EisensteinInteger
:+ (Integer
b forall a. Num a => a -> a -> a
+ Integer
d)
* :: EisensteinInteger -> EisensteinInteger -> EisensteinInteger
(*) (Integer
a :+ Integer
b) (Integer
c :+ Integer
d) = (Integer
a forall a. Num a => a -> a -> a
* Integer
c forall a. Num a => a -> a -> a
- Integer
b forall a. Num a => a -> a -> a
* Integer
d) Integer -> Integer -> EisensteinInteger
:+ (Integer
b forall a. Num a => a -> a -> a
* (Integer
c forall a. Num a => a -> a -> a
- Integer
d) forall a. Num a => a -> a -> a
+ Integer
a forall a. Num a => a -> a -> a
* Integer
d)
abs :: EisensteinInteger -> EisensteinInteger
abs = forall a b. (a, b) -> a
fst 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 = forall a b. (a, b) -> b
snd forall b c a. (b -> c) -> (a -> b) -> a -> c
. EisensteinInteger -> (EisensteinInteger, EisensteinInteger)
absSignum
instance S.Semiring EisensteinInteger where
plus :: EisensteinInteger -> EisensteinInteger -> EisensteinInteger
plus = forall a. Num a => a -> a -> a
(+)
times :: EisensteinInteger -> EisensteinInteger -> EisensteinInteger
times = 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 = 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 forall a. Ord a => a -> a -> Bool
> Integer
b Bool -> Bool -> Bool
&& Integer
b forall a. Ord a => a -> a -> Bool
>= Integer
0 = (EisensteinInteger
z, EisensteinInteger
1)
| Integer
b forall a. Ord a => a -> a -> Bool
>= Integer
a Bool -> Bool -> Bool
&& Integer
a forall a. Ord a => a -> a -> Bool
> Integer
0 = (Integer
b Integer -> Integer -> EisensteinInteger
:+ (Integer
b forall a. Num a => a -> a -> a
- Integer
a), Integer
1 Integer -> Integer -> EisensteinInteger
:+ Integer
1)
| Integer
b forall a. Ord a => a -> a -> Bool
> Integer
0 Bool -> Bool -> Bool
&& Integer
0 forall a. Ord a => a -> a -> Bool
>= Integer
a = ((Integer
b forall a. Num a => a -> a -> a
- Integer
a) Integer -> Integer -> EisensteinInteger
:+ (-Integer
a), Integer
0 Integer -> Integer -> EisensteinInteger
:+ Integer
1)
| Integer
a forall a. Ord a => a -> a -> Bool
< Integer
b Bool -> Bool -> Bool
&& Integer
b forall a. Ord a => a -> a -> Bool
<= Integer
0 = (-EisensteinInteger
z, -EisensteinInteger
1)
| Integer
b forall a. Ord a => a -> a -> Bool
<= Integer
a Bool -> Bool -> Bool
&& Integer
a forall a. Ord a => a -> a -> Bool
< Integer
0 = ((-Integer
b) Integer -> Integer -> EisensteinInteger
:+ (Integer
a forall a. Num a => a -> a -> a
- Integer
b), (-Integer
1) Integer -> Integer -> EisensteinInteger
:+ (-Integer
1))
| Bool
otherwise = ((Integer
a 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 = forall a. Int -> [a] -> [a]
take Int
6 (forall a. (a -> a) -> a -> [a]
iterate ((EisensteinInteger
1 forall a. Num a => a -> a -> a
+ EisensteinInteger
ω) *) EisensteinInteger
1)
associates :: EisensteinInteger -> [EisensteinInteger]
associates :: EisensteinInteger -> [EisensteinInteger]
associates EisensteinInteger
e = forall a b. (a -> b) -> [a] -> [b]
map (EisensteinInteger
e *) [EisensteinInteger]
ids
instance GcdDomain EisensteinInteger
instance Euclidean EisensteinInteger where
degree :: EisensteinInteger -> Natural
degree = forall a. Num a => Integer -> a
fromInteger 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 forall a. Num a => a -> a -> a
- EisensteinInteger
q forall a. Num a => a -> a -> a
* EisensteinInteger
y)
where
(EisensteinInteger
q, EisensteinInteger
_) = EisensteinInteger
-> Integer -> (EisensteinInteger, EisensteinInteger)
quotRemInt (EisensteinInteger
x 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 forall a. Num a => a -> a -> a
- Integer
bumpA) Integer -> Integer -> EisensteinInteger
:+ (Integer
rb forall a. Num a => a -> a -> a
- Integer
bumpB))
where
halfC :: Integer
halfC = forall a. Num a => a -> a
abs Integer
c forall a. Euclidean a => a -> a -> a
`quot` Integer
2
bumpA :: Integer
bumpA = forall a. Num a => a -> a
signum Integer
a forall a. Num a => a -> a -> a
* Integer
halfC
bumpB :: Integer
bumpB = forall a. Num a => a -> a
signum Integer
b forall a. Num a => a -> a -> a
* Integer
halfC
(Integer
qa, Integer
ra) = (Integer
a forall a. Num a => a -> a -> a
+ Integer
bumpA) forall a. Euclidean a => a -> a -> (a, a)
`quotRem` Integer
c
(Integer
qb, Integer
rb) = (Integer
b forall a. Num a => a -> a -> a
+ Integer
bumpB) forall a. Euclidean a => a -> a -> (a, a)
`quotRem` Integer
c
conjugate :: EisensteinInteger -> EisensteinInteger
conjugate :: EisensteinInteger -> EisensteinInteger
conjugate (Integer
a :+ Integer
b) = (Integer
a 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
aforall a. Num a => a -> a -> a
*Integer
a forall a. Num a => a -> a -> a
- Integer
a forall a. Num a => a -> a -> a
* Integer
b forall a. Num a => a -> a -> a
+ Integer
bforall a. Num a => a -> a -> a
*Integer
b
isPrime :: EisensteinInteger -> Bool
isPrime :: EisensteinInteger -> Bool
isPrime EisensteinInteger
e | EisensteinInteger
e forall a. Eq a => a -> a -> Bool
== EisensteinInteger
0 = Bool
False
| Integer
a' forall a. Eq a => a -> a -> Bool
== Integer
2 Bool -> Bool -> Bool
&& Integer
b' forall a. Eq a => a -> a -> Bool
== Integer
1 = Bool
True
| Integer
b' forall a. Eq a => a -> a -> Bool
== Integer
0 Bool -> Bool -> Bool
&& Integer
a' forall a. Integral a => a -> a -> a
`mod` Integer
3 forall a. Eq a => a -> a -> Bool
== Integer
2 = forall a. Maybe a -> Bool
isJust forall a b. (a -> b) -> a -> b
$ forall a. UniqueFactorisation a => a -> Maybe (Prime a)
U.isPrime Integer
a'
| Integer
nE forall a. Integral a => a -> a -> a
`mod` Integer
3 forall a. Eq a => a -> a -> Bool
== Integer
1 = forall a. Maybe a -> Bool
isJust forall a b. (a -> b) -> a -> b
$ 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' = 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 forall a. Eq a => a -> a -> Bool
== Integer
0 Bool -> Bool -> Bool
&& Integer
r2 forall a. Eq a => a -> a -> Bool
== Integer
0 = Word -> EisensteinInteger -> (Word, EisensteinInteger)
go (Word
n forall a. Num a => a -> a -> a
+ Word
1) (Integer
q1 Integer -> Integer -> EisensteinInteger
:+ Integer
q2)
| Bool
otherwise = (Word
n, forall a. Num a => a -> a
abs EisensteinInteger
z)
where
(Integer
q1, Integer
r1) = forall a. Integral a => a -> a -> (a, a)
divMod (Integer
a forall a. Num a => a -> a -> a
+ Integer
a forall a. Num a => a -> a -> a
- Integer
b) Integer
3
(Integer
q2, Integer
r2) = forall a. Integral a => a -> a -> (a, a)
divMod (Integer
a 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 forall a. Num a => a -> a -> a
* Integer
q forall a. Num a => a -> a -> a
* Integer
q forall a. Num a => a -> a -> a
- Integer
1) Prime Integer
p) of
(Integer
1, Integer
z : [Integer]
_) -> forall a. a -> Prime a
Prime forall a b. (a -> b) -> a -> b
$ forall a. Num a => a -> a
abs forall a b. (a -> b) -> a -> b
$ forall a. GcdDomain a => a -> a -> a
gcd (forall a. Prime a -> a
unPrime Prime Integer
p Integer -> Integer -> EisensteinInteger
:+ Integer
0) ((Integer
z forall a. Num a => a -> a -> a
- Integer
3 forall a. Num a => a -> a -> a
* Integer
q) Integer -> Integer -> EisensteinInteger
:+ Integer
1)
(Integer, [Integer])
_ -> forall a. HasCallStack => String -> a
error String
"findPrime: argument must be prime p = 6k + 1"
where
(Integer
q, Integer
r) = forall a. Prime a -> a
unPrime Prime Integer
p forall a. Euclidean a => a -> a -> (a, a)
`quotRem` Integer
6
primes :: Infinite (Prime EisensteinInteger)
primes :: Infinite (Prime EisensteinInteger)
primes = coerce :: forall a b. Coercible a b => a -> b
coerce forall a b. (a -> b) -> a -> b
$ (Integer
2 Integer -> Integer -> EisensteinInteger
:+ Integer
1) forall a. a -> Infinite a -> Infinite a
:< forall a.
(a -> a -> Ordering) -> Infinite a -> Infinite a -> Infinite a
mergeBy (forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing EisensteinInteger -> Integer
norm) Infinite EisensteinInteger
l Infinite EisensteinInteger
r
where
leftPrimes, rightPrimes :: Infinite (Prime Integer)
(Infinite (Prime Integer)
leftPrimes, Infinite (Prime Integer)
rightPrimes) = forall a. (a -> Bool) -> Infinite a -> (Infinite a, Infinite a)
Inf.partition (\Prime Integer
p -> forall a. Prime a -> a
unPrime Prime Integer
p forall a. Integral a => a -> a -> a
`mod` Integer
3 forall a. Eq a => a -> a -> Bool
== Integer
2) (forall a.
(Bits a, Integral a, UniqueFactorisation a) =>
a -> Prime a
U.nextPrime Integer
2...)
rightPrimes' :: Infinite (Prime Integer)
rightPrimes' :: Infinite (Prime Integer)
rightPrimes' = forall a. (a -> Bool) -> Infinite a -> Infinite a
Inf.filter (\Prime Integer
prime -> forall a. Prime a -> a
unPrime Prime Integer
prime forall a. Integral a => a -> a -> a
`mod` Integer
3 forall a. Eq a => a -> a -> Bool
== Integer
1) forall a b. (a -> b) -> a -> b
$ forall a. Infinite a -> Infinite a
Inf.tail Infinite (Prime Integer)
rightPrimes
l :: Infinite EisensteinInteger
l :: Infinite EisensteinInteger
l = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\Prime Integer
p -> forall a. Prime a -> a
unPrime Prime Integer
p Integer -> Integer -> EisensteinInteger
:+ Integer
0) Infinite (Prime Integer)
leftPrimes
r :: Infinite EisensteinInteger
r :: Infinite EisensteinInteger
r = forall a b. (a -> NonEmpty b) -> Infinite a -> Infinite b
Inf.concatMap
(\Prime Integer
p -> let Integer
x :+ Integer
y = forall a. Prime a -> a
unPrime (Prime Integer -> Prime EisensteinInteger
findPrime Prime Integer
p) in (Integer
x Integer -> Integer -> EisensteinInteger
:+ Integer
y) forall a. a -> [a] -> NonEmpty a
:| [Integer
x Integer -> Integer -> EisensteinInteger
:+ (Integer
x forall a. Num a => a -> a -> a
- Integer
y)])
Infinite (Prime Integer)
rightPrimes'
factorise :: EisensteinInteger -> [(Prime EisensteinInteger, Word)]
factorise :: EisensteinInteger -> [(Prime EisensteinInteger, Word)]
factorise EisensteinInteger
g = forall (t :: * -> *) a. Foldable t => t [a] -> [a]
concat forall a b. (a -> b) -> a -> b
$
forall a b. (a, b) -> b
snd forall a b. (a -> b) -> a -> b
$
forall (t :: * -> *) s a b.
Traversable t =>
(s -> a -> (s, b)) -> s -> t a -> (s, t b)
mapAccumL EisensteinInteger
-> (Prime Integer, Word)
-> (EisensteinInteger, [(Prime EisensteinInteger, Word)])
go (forall a. Num a => a -> a
abs EisensteinInteger
g) (forall a. UniqueFactorisation a => a -> [(Prime a, Word)]
U.factorise 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 forall a. Eq a => a -> a -> Bool
== Word
n = (EisensteinInteger
q, [(forall a. a -> Prime a
Prime (Integer
2 Integer -> Integer -> EisensteinInteger
:+ Integer
1), Word
e)])
| Bool
otherwise = forall a. HasCallStack => String -> a
error forall a b. (a -> b) -> a -> b
$ String
"3 is a prime factor of the norm of z = " forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> String
show EisensteinInteger
z
forall a. [a] -> [a] -> [a]
++ String
" with multiplicity " forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> String
show Word
e
forall a. [a] -> [a] -> [a]
++ String
" but (1 - ω) only divides z " forall a. [a] -> [a] -> [a]
++ forall a. Show a => a -> String
show Word
n 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)
| forall a. Prime a -> a
unPrime Prime Integer
p forall a. Integral a => a -> a -> a
`mod` Integer
3 forall a. Eq a => a -> a -> Bool
== Integer
2
= let e' :: Word
e' = Word
e forall a. Euclidean a => a -> a -> a
`quot` Word
2 in (EisensteinInteger
z EisensteinInteger -> Integer -> EisensteinInteger
`quotI` (forall a. Prime a -> a
unPrime Prime Integer
p forall a b. (Num a, Integral b) => a -> b -> a
^ Word
e'), [(forall a. a -> Prime a
Prime (forall a. Prime a -> a
unPrime Prime Integer
p Integer -> Integer -> EisensteinInteger
:+ Integer
0), Word
e')])
| Bool
otherwise = (EisensteinInteger
z', forall a. (a -> Bool) -> [a] -> [a]
filter ((forall a. Ord a => a -> a -> Bool
> Word
0) forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = forall a. Prime a -> a
unPrime Prime EisensteinInteger
gp
gp' :: Prime EisensteinInteger
gp' = forall a. a -> Prime a
Prime (Integer
x Integer -> Integer -> EisensteinInteger
:+ (Integer
x 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' (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 forall a. Euclidean a => a -> a -> a
`quot` Integer
n Integer -> Integer -> EisensteinInteger
:+ Integer
b 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 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 forall a. Num a => a -> a -> a
- Word
2) (Word
d forall a. Num a => a -> a -> a
+ Word
1) EisensteinInteger
z'
go Word
c Word
d EisensteinInteger
z = (Word
d forall a. Num a => a -> a -> a
+ Word
d1, Word
d 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 forall a. Num a => a -> a -> a
- Word
d1
z'' :: EisensteinInteger
z'' = forall a. (a -> a) -> a -> [a]
iterate (\EisensteinInteger
g -> forall a. a -> Maybe a -> a
fromMaybe EisensteinInteger
err forall a b. (a -> b) -> a -> b
$ (EisensteinInteger
g forall a. Num a => a -> a -> a
* forall a. Prime a -> a
unPrime Prime EisensteinInteger
p) EisensteinInteger -> Integer -> Maybe EisensteinInteger
`quotEvenI` Integer
np) EisensteinInteger
z' forall a. [a] -> Int -> a
!! 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 forall a. Num a => a -> a -> a
* forall a. Prime a -> a
unPrime Prime EisensteinInteger
p') EisensteinInteger -> Integer -> Maybe EisensteinInteger
`quotEvenI` Integer
np
= Word -> Word -> EisensteinInteger -> (Word, EisensteinInteger)
go1 (Word
c forall a. Num a => a -> a -> a
- Word
1) (Word
d forall a. Num a => a -> a -> a
+ Word
1) EisensteinInteger
z'
| Bool
otherwise
= (Word
d, EisensteinInteger
z)
err :: EisensteinInteger
err = forall a. HasCallStack => String -> a
error forall a b. (a -> b) -> a -> b
$ String
"divideByPrime: malformed arguments" forall a. [a] -> [a] -> [a]
++ 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 forall a. Eq a => a -> a -> Bool
== Integer
0 , Integer
yr forall a. Eq a => a -> a -> Bool
== Integer
0 = forall a. a -> Maybe a
Just (Integer
xq Integer -> Integer -> EisensteinInteger
:+ Integer
yq)
| Bool
otherwise = forall a. Maybe a
Nothing
where
(Integer
xq, Integer
xr) = Integer
x forall a. Euclidean a => a -> a -> (a, a)
`quotRem` Integer
n
(Integer
yq, Integer
yr) = Integer
y 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 = coerce :: forall a b. Coercible a b => a -> b
coerce 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 forall a. a -> Maybe a
Just (forall a. a -> Prime a
Prime EisensteinInteger
e) else forall a. Maybe a
Nothing