{-# 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
(EisensteinInteger -> EisensteinInteger -> Bool)
-> (EisensteinInteger -> EisensteinInteger -> Bool)
-> Eq EisensteinInteger
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: EisensteinInteger -> EisensteinInteger -> Bool
== :: EisensteinInteger -> EisensteinInteger -> Bool
$c/= :: EisensteinInteger -> EisensteinInteger -> Bool
/= :: 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
$ccompare :: EisensteinInteger -> EisensteinInteger -> Ordering
compare :: EisensteinInteger -> EisensteinInteger -> Ordering
$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
>= :: EisensteinInteger -> EisensteinInteger -> Bool
$cmax :: EisensteinInteger -> EisensteinInteger -> EisensteinInteger
max :: EisensteinInteger -> EisensteinInteger -> EisensteinInteger
$cmin :: EisensteinInteger -> EisensteinInteger -> EisensteinInteger
min :: EisensteinInteger -> EisensteinInteger -> 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
$cfrom :: forall x. EisensteinInteger -> Rep EisensteinInteger x
from :: forall x. EisensteinInteger -> Rep EisensteinInteger x
$cto :: forall x. Rep EisensteinInteger x -> EisensteinInteger
to :: forall x. Rep EisensteinInteger x -> EisensteinInteger
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
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]
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 :: Infinite (Prime EisensteinInteger)
primes :: Infinite (Prime EisensteinInteger)
primes = Infinite EisensteinInteger -> Infinite (Prime EisensteinInteger)
forall a b. Coercible a b => a -> b
coerce (Infinite EisensteinInteger -> Infinite (Prime EisensteinInteger))
-> Infinite EisensteinInteger -> Infinite (Prime EisensteinInteger)
forall a b. (a -> b) -> a -> b
$ (Integer
2 Integer -> Integer -> EisensteinInteger
:+ Integer
1) EisensteinInteger
-> Infinite EisensteinInteger -> Infinite EisensteinInteger
forall a. a -> Infinite a -> Infinite a
:< (EisensteinInteger -> EisensteinInteger -> Ordering)
-> Infinite EisensteinInteger
-> Infinite EisensteinInteger
-> Infinite EisensteinInteger
forall a.
(a -> a -> Ordering) -> Infinite a -> Infinite a -> Infinite a
mergeBy ((EisensteinInteger -> Integer)
-> EisensteinInteger -> EisensteinInteger -> Ordering
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) = (Prime Integer -> Bool)
-> Infinite (Prime Integer)
-> (Infinite (Prime Integer), Infinite (Prime Integer))
forall a. (a -> Bool) -> Infinite a -> (Infinite a, Infinite a)
Inf.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' :: Infinite (Prime Integer)
rightPrimes' :: Infinite (Prime Integer)
rightPrimes' = (Prime Integer -> Bool)
-> Infinite (Prime Integer) -> Infinite (Prime Integer)
forall a. (a -> Bool) -> Infinite a -> Infinite a
Inf.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) (Infinite (Prime Integer) -> Infinite (Prime Integer))
-> Infinite (Prime Integer) -> Infinite (Prime Integer)
forall a b. (a -> b) -> a -> b
$ Infinite (Prime Integer) -> Infinite (Prime Integer)
forall a. Infinite a -> Infinite a
Inf.tail Infinite (Prime Integer)
rightPrimes
l :: Infinite EisensteinInteger
l :: Infinite EisensteinInteger
l = (Prime Integer -> EisensteinInteger)
-> Infinite (Prime Integer) -> Infinite EisensteinInteger
forall a b. (a -> b) -> Infinite a -> Infinite b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (\Prime Integer
p -> Prime Integer -> Integer
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 = (Prime Integer -> NonEmpty EisensteinInteger)
-> Infinite (Prime Integer) -> Infinite EisensteinInteger
forall a b. (a -> NonEmpty b) -> Infinite a -> Infinite b
Inf.concatMap
(\Prime Integer
p -> let Integer
x :+ Integer
y = Prime EisensteinInteger -> EisensteinInteger
forall a. Prime a -> a
unPrime (Prime Integer -> Prime EisensteinInteger
findPrime Prime Integer
p) in (Integer
x Integer -> Integer -> EisensteinInteger
:+ Integer
y) EisensteinInteger
-> [EisensteinInteger] -> NonEmpty EisensteinInteger
forall a. a -> [a] -> NonEmpty a
:| [Integer
x Integer -> Integer -> EisensteinInteger
:+ (Integer
x Integer -> Integer -> Integer
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 = [[(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 :: * -> *) 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 (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. HasCallStack => [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)]
forall a b. Coercible a b => a -> b
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