{- |
module: Factor.Nfzw
description: The subring Z[w] of the number field Q(w)
license: MIT

maintainer: Joe Leslie-Hurd <joe@gilith.com>
stability: provisional
portability: portable
-}
module Factor.Nfzw
where

import qualified Factor.Gfpx as Gfpx
import Factor.Prime (Gfp,Prime)
import qualified Factor.Prime as Prime
import Factor.Util
import Factor.Zx (Zx)
import qualified Factor.Zx as Zx

-------------------------------------------------------------------------------
-- Elements of Z[w] having the form a + b*w with a and b coprime integers
-------------------------------------------------------------------------------

data Nfzw = Nfzw Integer Integer
  deriving (Nfzw -> Nfzw -> Bool
(Nfzw -> Nfzw -> Bool) -> (Nfzw -> Nfzw -> Bool) -> Eq Nfzw
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Nfzw -> Nfzw -> Bool
$c/= :: Nfzw -> Nfzw -> Bool
== :: Nfzw -> Nfzw -> Bool
$c== :: Nfzw -> Nfzw -> Bool
Eq,Eq Nfzw
Eq Nfzw
-> (Nfzw -> Nfzw -> Ordering)
-> (Nfzw -> Nfzw -> Bool)
-> (Nfzw -> Nfzw -> Bool)
-> (Nfzw -> Nfzw -> Bool)
-> (Nfzw -> Nfzw -> Bool)
-> (Nfzw -> Nfzw -> Nfzw)
-> (Nfzw -> Nfzw -> Nfzw)
-> Ord Nfzw
Nfzw -> Nfzw -> Bool
Nfzw -> Nfzw -> Ordering
Nfzw -> Nfzw -> Nfzw
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 :: Nfzw -> Nfzw -> Nfzw
$cmin :: Nfzw -> Nfzw -> Nfzw
max :: Nfzw -> Nfzw -> Nfzw
$cmax :: Nfzw -> Nfzw -> Nfzw
>= :: Nfzw -> Nfzw -> Bool
$c>= :: Nfzw -> Nfzw -> Bool
> :: Nfzw -> Nfzw -> Bool
$c> :: Nfzw -> Nfzw -> Bool
<= :: Nfzw -> Nfzw -> Bool
$c<= :: Nfzw -> Nfzw -> Bool
< :: Nfzw -> Nfzw -> Bool
$c< :: Nfzw -> Nfzw -> Bool
compare :: Nfzw -> Nfzw -> Ordering
$ccompare :: Nfzw -> Nfzw -> Ordering
$cp1Ord :: Eq Nfzw
Ord)

instance Show Nfzw where
  show :: Nfzw -> String
show Nfzw
x = case Nfzw
x of
             Nfzw Integer
a Integer
0 -> Integer -> String
forall a. Show a => a -> String
show Integer
a
             Nfzw Integer
0 Integer
b -> Integer -> String
forall a. (Eq a, Num a, Show a) => a -> String
showW Integer
b
             Nfzw Integer
a Integer
b | Integer
b Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
0 -> Integer -> String
forall a. Show a => a -> String
show Integer
a String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" - " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Integer -> String
forall a. (Eq a, Num a, Show a) => a -> String
showW (-Integer
b)
             Nfzw Integer
a Integer
b | Bool
otherwise -> Integer -> String
forall a. Show a => a -> String
show Integer
a String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" + " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Integer -> String
forall a. (Eq a, Num a, Show a) => a -> String
showW Integer
b
    where
      showW :: a -> String
showW a
1 = String
"w"
      showW (-1) = String
"-w"
      showW a
i = a -> String
forall a. Show a => a -> String
show a
i String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
"w"

valid :: Nfzw -> Bool
valid :: Nfzw -> Bool
valid (Nfzw Integer
0 Integer
0) = Bool
True
valid (Nfzw Integer
a Integer
b) = Integer -> Integer -> Bool
coprime Integer
a Integer
b

-------------------------------------------------------------------------------
-- Valid elements a + bw where b > 0
-------------------------------------------------------------------------------

filterValidLine :: (Nfzw -> Bool) -> Integer -> [Nfzw]
filterValidLine :: (Nfzw -> Bool) -> Integer -> [Nfzw]
filterValidLine Nfzw -> Bool
p Integer
k =
    (Nfzw -> Bool) -> [Nfzw] -> [Nfzw]
forall a. (a -> Bool) -> [a] -> [a]
filter (\Nfzw
x -> Nfzw -> Bool
valid Nfzw
x Bool -> Bool -> Bool
&& Nfzw -> Bool
p Nfzw
x) ([Nfzw] -> [Nfzw]) -> [Nfzw] -> [Nfzw]
forall a b. (a -> b) -> a -> b
$
    (Integer -> Nfzw) -> [Integer] -> [Nfzw]
forall a b. (a -> b) -> [a] -> [b]
map (\Integer
a -> Integer -> Integer -> Nfzw
Nfzw Integer
a (Integer
k Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
1 Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
- Integer -> Integer
forall a. Num a => a -> a
abs Integer
a)) [(-Integer
k)..Integer
k]

filterValid :: (Nfzw -> Bool) -> [Nfzw]
filterValid :: (Nfzw -> Bool) -> [Nfzw]
filterValid Nfzw -> Bool
p = (Integer -> [Nfzw]) -> [Integer] -> [Nfzw]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap ((Nfzw -> Bool) -> Integer -> [Nfzw]
filterValidLine Nfzw -> Bool
p) [Integer
0..]

-------------------------------------------------------------------------------
-- Ring operations
-------------------------------------------------------------------------------

zero :: Nfzw
zero :: Nfzw
zero = Integer -> Integer -> Nfzw
Nfzw Integer
0 Integer
0

isZero :: Nfzw -> Bool
isZero :: Nfzw -> Bool
isZero Nfzw
x = Nfzw
x Nfzw -> Nfzw -> Bool
forall a. Eq a => a -> a -> Bool
== Nfzw
zero

negate :: Nfzw -> Nfzw
negate :: Nfzw -> Nfzw
negate (Nfzw Integer
a Integer
b) = Integer -> Integer -> Nfzw
Nfzw (Integer -> Integer
forall a. Num a => a -> a
Prelude.negate Integer
a) (Integer -> Integer
forall a. Num a => a -> a
Prelude.negate Integer
b)

-------------------------------------------------------------------------------
-- Ring homomorphisms from a + bw to Z
-------------------------------------------------------------------------------

toInteger :: Integer -> Nfzw -> Integer
toInteger :: Integer -> Nfzw -> Integer
toInteger Integer
m (Nfzw Integer
a Integer
b) = Integer
a Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
bInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
m

-------------------------------------------------------------------------------
-- The norm of an element a - bw is b^degree(f) * f(a/b)
-------------------------------------------------------------------------------

norm :: Zx -> Nfzw -> Integer
norm :: Zx -> Nfzw -> Integer
norm Zx
f (Nfzw Integer
a Integer
b) =
    (Integer, Integer) -> Integer
forall a b. (a, b) -> a
fst ((Integer, Integer) -> Integer) -> (Integer, Integer) -> Integer
forall a b. (a -> b) -> a -> b
$ Int -> (Int, Integer, Integer) -> (Integer, Integer)
forall a.
Integral a =>
a -> (a, Integer, Integer) -> (Integer, Integer)
align Int
0 ((Int, Integer, Integer) -> (Integer, Integer))
-> (Int, Integer, Integer) -> (Integer, Integer)
forall a b. (a -> b) -> a -> b
$ ((Int, Integer)
 -> (Int, Integer, Integer) -> (Int, Integer, Integer))
-> (Int, Integer, Integer)
-> [(Int, Integer)]
-> (Int, Integer, Integer)
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (Int, Integer)
-> (Int, Integer, Integer) -> (Int, Integer, Integer)
forall a.
Integral a =>
(a, Integer) -> (a, Integer, Integer) -> (a, Integer, Integer)
fma (Int
0,Integer
0,Integer
1) ([(Int, Integer)] -> (Int, Integer, Integer))
-> [(Int, Integer)] -> (Int, Integer, Integer)
forall a b. (a -> b) -> a -> b
$ Zx -> [(Int, Integer)]
Zx.monomials Zx
f
  where
    fma :: (a, Integer) -> (a, Integer, Integer) -> (a, Integer, Integer)
fma (a
i,Integer
c) (a, Integer, Integer)
z = (a
i, Integer
ni Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
cInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Integer
bi, Integer
bi) where (Integer
ni,Integer
bi) = a -> (a, Integer, Integer) -> (Integer, Integer)
forall a.
Integral a =>
a -> (a, Integer, Integer) -> (Integer, Integer)
align a
i (a, Integer, Integer)
z

    align :: a -> (a, Integer, Integer) -> (Integer, Integer)
align a
i (a
d,Integer
nd,Integer
bd) = if a
k a -> a -> Bool
forall a. Ord a => a -> a -> Bool
<= a
0 then (Integer
nd,Integer
bd) else (Integer
ni,Integer
bi)
      where
        k :: a
k = a
d a -> a -> a
forall a. Num a => a -> a -> a
- a
i
        ni :: Integer
ni = Integer
nd Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
aInteger -> a -> Integer
forall a b. (Num a, Integral b) => a -> b -> a
^a
k
        bi :: Integer
bi = Integer
bd Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
b'Integer -> a -> Integer
forall a b. (Num a, Integral b) => a -> b -> a
^a
k

    b' :: Integer
b' = Integer -> Integer
forall a. Num a => a -> a
Prelude.negate Integer
b

-------------------------------------------------------------------------------
-- First degree prime ideals of Z[w]
--
-- These have norm p for some prime integer p, and are in bijective
-- correspondence with pairs (r,p) where f(r) == 0 (mod p)
--
-- Elements of the form a + b*w have the property that their principal
-- ideal uniquely factors into first degree prime ideals
--
--   <a + b*w> == (r1,p1)^e1 * ... * (rn,pn)^en
--
-- where
--
--   |norm (a + b*w)| == p1^e1 * ... * pn^en
--
-- and
--
--   a + b*ri == 0 (mod pi) for every 1 <= i <= n
--
-- Note that this last property implies that the pi are all distinct
-- prime integers, since at most one value of r can satisfy the
-- equation.
-------------------------------------------------------------------------------

type Ideal = (Gfp,Prime)

ideals :: Zx -> [Ideal]
ideals :: Zx -> [(Integer, Integer)]
ideals Zx
f = (Integer -> [(Integer, Integer)])
-> [Integer] -> [(Integer, Integer)]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap Integer -> [(Integer, Integer)]
roots [Integer]
Prime.primes
  where roots :: Integer -> [(Integer, Integer)]
roots Integer
p = (Integer -> (Integer, Integer))
-> [Integer] -> [(Integer, Integer)]
forall a b. (a -> b) -> [a] -> [b]
map (\Integer
r -> (Integer
r,Integer
p)) ([Integer] -> [(Integer, Integer)])
-> [Integer] -> [(Integer, Integer)]
forall a b. (a -> b) -> a -> b
$ Integer -> Gfpx -> [Integer]
Gfpx.roots Integer
p (Integer -> Zx -> Gfpx
Gfpx.fromZx Integer
p Zx
f)

inIdeal :: Nfzw -> Ideal -> Bool
inIdeal :: Nfzw -> (Integer, Integer) -> Bool
inIdeal (Nfzw Integer
a Integer
b) (Integer
r,Integer
p) =
    Integer -> Integer -> Integer -> Integer
Prime.add Integer
p Integer
a' (Integer -> Integer -> Integer -> Integer
Prime.multiply Integer
p Integer
r Integer
b') Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0
  where
    a' :: Integer
a' = Integer -> Integer -> Integer
Prime.fromInteger Integer
p Integer
a
    b' :: Integer
b' = Integer -> Integer -> Integer
Prime.fromInteger Integer
p Integer
b

factor :: Zx -> [Ideal] -> Nfzw -> ([(Ideal,Integer)],Integer)
factor :: Zx
-> [(Integer, Integer)]
-> Nfzw
-> ([((Integer, Integer), Integer)], Integer)
factor Zx
f [(Integer, Integer)]
rps0 Nfzw
x = [(Integer, Integer)]
-> Integer -> ([((Integer, Integer), Integer)], Integer)
go [(Integer, Integer)]
rps0 (Zx -> Nfzw -> Integer
norm Zx
f Nfzw
x)
  where
    go :: [(Integer, Integer)]
-> Integer -> ([((Integer, Integer), Integer)], Integer)
go [(Integer, Integer)]
_ Integer
n | Integer -> Integer
forall a. Num a => a -> a
abs Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
<= Integer
1 = ([],Integer
n)
    go [] Integer
n = ([],Integer
n)
    go ((Integer, Integer)
rp : [(Integer, Integer)]
rps) Integer
n = (if Integer
k Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
0 then [((Integer, Integer), Integer)]
rpks else ((Integer, Integer), Integer)
rpk ((Integer, Integer), Integer)
-> [((Integer, Integer), Integer)]
-> [((Integer, Integer), Integer)]
forall a. a -> [a] -> [a]
: [((Integer, Integer), Integer)]
rpks, Integer
s)
      where
        p :: Integer
p = (Integer, Integer) -> Integer
forall a b. (a, b) -> b
snd (Integer, Integer)
rp
        (Integer
k,Integer
m) = Integer -> Integer -> (Integer, Integer)
divPower Integer
p Integer
n
        ([((Integer, Integer), Integer)]
rpks,Integer
s) = [(Integer, Integer)]
-> Integer -> ([((Integer, Integer), Integer)], Integer)
go [(Integer, Integer)]
rps2 Integer
m
        ([(Integer, Integer)]
rps1,[(Integer, Integer)]
rps2) = ((Integer, Integer) -> Bool)
-> [(Integer, Integer)]
-> ([(Integer, Integer)], [(Integer, Integer)])
forall a. (a -> Bool) -> [a] -> ([a], [a])
span (Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
(==) Integer
p (Integer -> Bool)
-> ((Integer, Integer) -> Integer) -> (Integer, Integer) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Integer, Integer) -> Integer
forall a b. (a, b) -> b
snd) [(Integer, Integer)]
rps
        rpk :: ((Integer, Integer), Integer)
rpk = case ((Integer, Integer) -> Bool)
-> [(Integer, Integer)] -> [(Integer, Integer)]
forall a. (a -> Bool) -> [a] -> [a]
filter (Nfzw -> (Integer, Integer) -> Bool
inIdeal Nfzw
x) ((Integer, Integer)
rp (Integer, Integer) -> [(Integer, Integer)] -> [(Integer, Integer)]
forall a. a -> [a] -> [a]
: [(Integer, Integer)]
rps1) of
                [] -> String -> ((Integer, Integer), Integer)
forall a. HasCallStack => String -> a
error String
"no ideal divides x"
                [(Integer, Integer)
i] -> ((Integer, Integer)
i,Integer
k)
                (Integer, Integer)
_ : (Integer, Integer)
_ : [(Integer, Integer)]
_ -> String -> ((Integer, Integer), Integer)
forall a. HasCallStack => String -> a
error String
"multiple ideals divide x"