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
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
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..]
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)
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
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
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"