{- |
module: Factor
description: Factoring integers and polynomials
license: MIT

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

import qualified Data.List as List
import System.Random (RandomGen)

import qualified Factor.Bz as Bz
import qualified Factor.Ec as Ec
import Factor.Gfpx (Gfpx)
import qualified Factor.Gfpx as Gfpx
import qualified Factor.Nfs as Nfs
import Factor.Prime (Prime,PrimePower)
import qualified Factor.Prime as Prime
import Factor.Term (Term(..))
import qualified Factor.Term as Term
import Factor.Util
import Factor.Value (Value(..))
import Factor.Zx (Zx)
import qualified Factor.Zx as Zx

-------------------------------------------------------------------------------
-- Factoring integers
-------------------------------------------------------------------------------

type IntegerFactorer r = Config -> Integer -> r -> Verbose ([PrimePower],r)

data Config =
    Config
      {Config -> Integer
trialDivisionConfig :: Integer,  -- Must be at least 3
       Config -> Config
ecmConfig :: Ec.Config,
       Config -> Config
nfsConfig :: Nfs.Config}
  deriving (Config -> Config -> Bool
(Config -> Config -> Bool)
-> (Config -> Config -> Bool) -> Eq Config
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Config -> Config -> Bool
$c/= :: Config -> Config -> Bool
== :: Config -> Config -> Bool
$c== :: Config -> Config -> Bool
Eq,Eq Config
Eq Config
-> (Config -> Config -> Ordering)
-> (Config -> Config -> Bool)
-> (Config -> Config -> Bool)
-> (Config -> Config -> Bool)
-> (Config -> Config -> Bool)
-> (Config -> Config -> Config)
-> (Config -> Config -> Config)
-> Ord Config
Config -> Config -> Bool
Config -> Config -> Ordering
Config -> Config -> Config
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 :: Config -> Config -> Config
$cmin :: Config -> Config -> Config
max :: Config -> Config -> Config
$cmax :: Config -> Config -> Config
>= :: Config -> Config -> Bool
$c>= :: Config -> Config -> Bool
> :: Config -> Config -> Bool
$c> :: Config -> Config -> Bool
<= :: Config -> Config -> Bool
$c<= :: Config -> Config -> Bool
< :: Config -> Config -> Bool
$c< :: Config -> Config -> Bool
compare :: Config -> Config -> Ordering
$ccompare :: Config -> Config -> Ordering
$cp1Ord :: Eq Config
Ord,Int -> Config -> ShowS
[Config] -> ShowS
Config -> String
(Int -> Config -> ShowS)
-> (Config -> String) -> ([Config] -> ShowS) -> Show Config
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Config] -> ShowS
$cshowList :: [Config] -> ShowS
show :: Config -> String
$cshow :: Config -> String
showsPrec :: Int -> Config -> ShowS
$cshowsPrec :: Int -> Config -> ShowS
Show)

defaultConfig :: Config
defaultConfig :: Config
defaultConfig =
    Config :: Integer -> Config -> Config -> Config
Config
      {trialDivisionConfig :: Integer
trialDivisionConfig = Integer
1000,
       ecmConfig :: Config
ecmConfig = Config
Ec.defaultConfig,
       nfsConfig :: Config
nfsConfig = Config
Nfs.defaultConfig}

powerInteger :: Integer -> Integer -> Maybe (Integer,Integer)
powerInteger :: Integer -> Integer -> Maybe (Integer, Integer)
powerInteger Integer
m Integer
n = [Integer] -> Maybe (Integer, Integer)
go [Integer]
Prime.primes
  where
    go :: [Integer] -> Maybe (Integer, Integer)
go [] = String -> Maybe (Integer, Integer)
forall a. HasCallStack => String -> a
error String
"ran out of primes"
    go (Integer
p : [Integer]
ps) =
        if Integer
r Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
<= Integer
m then Maybe (Integer, Integer)
forall a. Maybe a
Nothing
        else if Integer
r Integer -> Integer -> Integer
forall a b. (Num a, Integral b) => a -> b -> a
^ Integer
p Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
/= Integer
n then [Integer] -> Maybe (Integer, Integer)
go [Integer]
ps
        else case Integer -> Integer -> Maybe (Integer, Integer)
powerInteger Integer
m Integer
r of
               Maybe (Integer, Integer)
Nothing -> (Integer, Integer) -> Maybe (Integer, Integer)
forall a. a -> Maybe a
Just (Integer
r,Integer
p)
               Just (Integer
s,Integer
k) -> (Integer, Integer) -> Maybe (Integer, Integer)
forall a. a -> Maybe a
Just (Integer
s, Integer
p Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
k)
      where
        r :: Integer
r = Integer -> Integer -> Integer
nthRoot Integer
p Integer
n

nfsFactorInteger :: RandomGen r => IntegerFactorer r
nfsFactorInteger :: IntegerFactorer r
nfsFactorInteger Config
cfg Integer
n r
r = do
    String -> Verbose ()
comment String
"Cranking up the number field sieve (NFS)"
    Maybe Integer
m <- Config -> Integer -> Verbose (Maybe Integer)
Nfs.factor (Config -> Config
nfsConfig Config
cfg) Integer
n
    case Maybe Integer
m of
      Maybe Integer
Nothing -> String -> Verbose ([(Integer, Integer)], r)
forall a. HasCallStack => String -> a
error String
"NFS factorization failed"
      Just Integer
g -> do
        Integer
h <- Integer -> Verbose Integer
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Integer -> Verbose Integer) -> Integer -> Verbose Integer
forall a b. (a -> b) -> a -> b
$ Integer
n Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`div` Integer
g
        String -> Verbose ()
comment (String -> Verbose ()) -> String -> Verbose ()
forall a b. (a -> b) -> a -> b
$ String
"NFS factorization: " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Integer -> String
forall a. Show a => a -> String
show Integer
g String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" * " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Integer -> String
forall a. Show a => a -> String
show Integer
h
        IntegerFactorer r
-> Config
-> Integer
-> Integer
-> r
-> Verbose ([(Integer, Integer)], r)
forall r.
RandomGen r =>
IntegerFactorer r
-> Config
-> Integer
-> Integer
-> r
-> Verbose ([(Integer, Integer)], r)
mergeFactorInteger IntegerFactorer r
forall r. RandomGen r => IntegerFactorer r
nfsFactorInteger Config
cfg Integer
g Integer
h r
r

ecmFactorInteger :: RandomGen r => IntegerFactorer r
ecmFactorInteger :: IntegerFactorer r
ecmFactorInteger Config
cfg Integer
n r
r = do
    String -> Verbose ()
comment String
"Firing up the elliptic curve method (ECM)"
    (Maybe Integer
m,r
r') <- Config -> Integer -> r -> Verbose (Maybe Integer, r)
forall r.
RandomGen r =>
Config -> Integer -> r -> Verbose (Maybe Integer, r)
Ec.factor (Config -> Config
ecmConfig Config
cfg) Integer
n r
r
    case Maybe Integer
m of
      Maybe Integer
Nothing -> IntegerFactorer r
forall r. RandomGen r => IntegerFactorer r
nfsFactorInteger Config
cfg Integer
n r
r'
      Just Integer
g -> do
        Integer
h <- Integer -> Verbose Integer
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Integer -> Verbose Integer) -> Integer -> Verbose Integer
forall a b. (a -> b) -> a -> b
$ Integer
n Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`div` Integer
g
        String -> Verbose ()
comment (String -> Verbose ()) -> String -> Verbose ()
forall a b. (a -> b) -> a -> b
$ String
"ECM factorization: " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Integer -> String
forall a. Show a => a -> String
show Integer
g String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" * " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Integer -> String
forall a. Show a => a -> String
show Integer
h
        IntegerFactorer r
-> Config
-> Integer
-> Integer
-> r
-> Verbose ([(Integer, Integer)], r)
forall r.
RandomGen r =>
IntegerFactorer r
-> Config
-> Integer
-> Integer
-> r
-> Verbose ([(Integer, Integer)], r)
mergeFactorInteger IntegerFactorer r
forall r. RandomGen r => IntegerFactorer r
ecmFactorInteger Config
cfg Integer
g Integer
h r
r'

primeFactorInteger :: RandomGen r => IntegerFactorer r -> IntegerFactorer r
primeFactorInteger :: IntegerFactorer r -> IntegerFactorer r
primeFactorInteger IntegerFactorer r
f Config
cfg Integer
n r
r =
    case Integer -> r -> (Bool, r)
forall r. RandomGen r => Integer -> r -> (Bool, r)
Prime.isPrime Integer
n r
r of
      (Bool
False,r
r') -> IntegerFactorer r
f Config
cfg Integer
n r
r'
      (Bool
True,r
r') -> do
        String -> Verbose ()
comment (String -> Verbose ()) -> String -> Verbose ()
forall a b. (a -> b) -> a -> b
$ String
"Prime: " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Integer -> String
forall a. Show a => a -> String
show Integer
n
        ([(Integer, Integer)], r) -> Verbose ([(Integer, Integer)], r)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (([(Integer, Integer)], r) -> Verbose ([(Integer, Integer)], r))
-> ([(Integer, Integer)], r) -> Verbose ([(Integer, Integer)], r)
forall a b. (a -> b) -> a -> b
$ ([(Integer
n,Integer
1)],r
r')

powerFactorInteger :: RandomGen r => IntegerFactorer r -> IntegerFactorer r
powerFactorInteger :: IntegerFactorer r -> IntegerFactorer r
powerFactorInteger IntegerFactorer r
_ Config
_ Integer
1 r
r = ([(Integer, Integer)], r) -> Verbose ([(Integer, Integer)], r)
forall (f :: * -> *) a. Applicative f => a -> f a
pure ([],r
r)
powerFactorInteger IntegerFactorer r
f Config
cfg Integer
n r
r = do
    String -> Verbose ()
comment (String -> Verbose ()) -> String -> Verbose ()
forall a b. (a -> b) -> a -> b
$ String
"Factor target is " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Integer -> String
widthIntegerToString Integer
n
    case Integer -> Integer -> Maybe (Integer, Integer)
powerInteger (Config -> Integer
trialDivisionConfig Config
cfg) Integer
n of
      Maybe (Integer, Integer)
Nothing -> IntegerFactorer r -> IntegerFactorer r
forall r. RandomGen r => IntegerFactorer r -> IntegerFactorer r
primeFactorInteger IntegerFactorer r
f Config
cfg Integer
n r
r
      Just (Integer
m,Integer
k) -> do
        String -> Verbose ()
comment (String -> Verbose ()) -> String -> Verbose ()
forall a b. (a -> b) -> a -> b
$ String
"Perfect power: " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Integer -> String
forall a. Show a => a -> String
show Integer
m String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
"^" String -> ShowS
forall a. [a] -> [a] -> [a]
++ Integer -> String
forall a. Show a => a -> String
show Integer
k
        String -> Verbose ()
comment (String -> Verbose ()) -> String -> Verbose ()
forall a b. (a -> b) -> a -> b
$ String
"Adjusted factor target is " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Integer -> String
widthIntegerToString Integer
m
        ([(Integer, Integer)]
pjs,r
r') <- IntegerFactorer r -> IntegerFactorer r
forall r. RandomGen r => IntegerFactorer r -> IntegerFactorer r
primeFactorInteger IntegerFactorer r
f Config
cfg Integer
m r
r
        ([(Integer, Integer)], r) -> Verbose ([(Integer, Integer)], r)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (([(Integer, Integer)], r) -> Verbose ([(Integer, Integer)], r))
-> ([(Integer, Integer)], r) -> Verbose ([(Integer, Integer)], r)
forall a b. (a -> b) -> a -> b
$ (((Integer, Integer) -> (Integer, Integer))
-> [(Integer, Integer)] -> [(Integer, Integer)]
forall a b. (a -> b) -> [a] -> [b]
map (\(Integer
p,Integer
j) -> (Integer
p, Integer
j Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
k)) [(Integer, Integer)]
pjs, r
r')

mergeFactorInteger ::
    RandomGen r => IntegerFactorer r ->
    Config -> Integer -> Integer -> r -> Verbose ([PrimePower],r)
mergeFactorInteger :: IntegerFactorer r
-> Config
-> Integer
-> Integer
-> r
-> Verbose ([(Integer, Integer)], r)
mergeFactorInteger IntegerFactorer r
f Config
cfg Integer
m Integer
n r
r | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
m = IntegerFactorer r
-> Config
-> Integer
-> Integer
-> r
-> Verbose ([(Integer, Integer)], r)
forall r.
RandomGen r =>
IntegerFactorer r
-> Config
-> Integer
-> Integer
-> r
-> Verbose ([(Integer, Integer)], r)
mergeFactorInteger IntegerFactorer r
f Config
cfg Integer
n Integer
m r
r
mergeFactorInteger IntegerFactorer r
f Config
cfg Integer
m Integer
n r
r = do
    ([(Integer, Integer)]
pks,r
r') <- IntegerFactorer r -> IntegerFactorer r
forall r. RandomGen r => IntegerFactorer r -> IntegerFactorer r
powerFactorInteger IntegerFactorer r
f Config
cfg Integer
m r
r
    ([(Integer, Integer)]
pks',r
r'') <- IntegerFactorer r -> IntegerFactorer r
forall r. RandomGen r => IntegerFactorer r -> IntegerFactorer r
powerFactorInteger IntegerFactorer r
f Config
cfg Integer
n r
r'
    ([(Integer, Integer)], r) -> Verbose ([(Integer, Integer)], r)
forall (f :: * -> *) a. Applicative f => a -> f a
pure ([(Integer, Integer)]
-> [(Integer, Integer)] -> [(Integer, Integer)]
Prime.multiplyPrimePowers [(Integer, Integer)]
pks [(Integer, Integer)]
pks', r
r'')

factorInteger :: RandomGen r => IntegerFactorer r
factorInteger :: IntegerFactorer r
factorInteger Config
_ Integer
n r
r | Integer -> Integer
forall a. Num a => a -> a
abs Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
<= Integer
1 = ([(Integer, Integer)], r) -> Verbose ([(Integer, Integer)], r)
forall (f :: * -> *) a. Applicative f => a -> f a
pure ([(Integer
n,Integer
1)],r
r)
factorInteger Config
cfg Integer
n r
r | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
0 = do
    ([(Integer, Integer)]
pks,r
r') <- IntegerFactorer r
forall r. RandomGen r => IntegerFactorer r
factorInteger Config
cfg (-Integer
n) r
r
    ([(Integer, Integer)], r) -> Verbose ([(Integer, Integer)], r)
forall (f :: * -> *) a. Applicative f => a -> f a
pure ((-Integer
1,Integer
1) (Integer, Integer) -> [(Integer, Integer)] -> [(Integer, Integer)]
forall a. a -> [a] -> [a]
: [(Integer, Integer)]
pks, r
r')
factorInteger Config
cfg Integer
n r
r = do
    String -> Verbose ()
comment (String -> Verbose ()) -> String -> Verbose ()
forall a b. (a -> b) -> a -> b
$ String
"Attempting to factor " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Integer -> String
widthIntegerToString Integer
n
    Integer
t <- Integer -> Verbose Integer
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Integer -> Verbose Integer) -> Integer -> Verbose Integer
forall a b. (a -> b) -> a -> b
$ Config -> Integer
trialDivisionConfig Config
cfg
    [Integer]
ps <- [Integer] -> Verbose [Integer]
forall (f :: * -> *) a. Applicative f => a -> f a
pure ([Integer] -> Verbose [Integer]) -> [Integer] -> Verbose [Integer]
forall a b. (a -> b) -> a -> b
$ (Integer -> Bool) -> [Integer] -> [Integer]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile (\Integer
p -> Integer
p Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
<= Integer
t) [Integer]
Prime.primes
    ([(Integer, Integer)]
pks,Integer
m) <- ([(Integer, Integer)], Integer)
-> Verbose ([(Integer, Integer)], Integer)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (([(Integer, Integer)], Integer)
 -> Verbose ([(Integer, Integer)], Integer))
-> ([(Integer, Integer)], Integer)
-> Verbose ([(Integer, Integer)], Integer)
forall a b. (a -> b) -> a -> b
$ [Integer] -> Integer -> ([(Integer, Integer)], Integer)
Prime.factor [Integer]
ps Integer
n
    String -> Verbose ()
comment (String -> Verbose ()) -> String -> Verbose ()
forall a b. (a -> b) -> a -> b
$
      String
"Trial division up to " String -> ShowS
forall a. [a] -> [a] -> [a]
++ Integer -> String
forall a. Show a => a -> String
show Integer
t String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" found " String -> ShowS
forall a. [a] -> [a] -> [a]
++
      (if [(Integer, Integer)] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [(Integer, Integer)]
pks then String
"no factors"
       else let l :: Int
l = [(Integer, Integer)] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [(Integer, Integer)]
pks in
            (if Integer
m Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 then String
"all prime factors"
             else Int -> String
forall a. Show a => a -> String
show Int
l String -> ShowS
forall a. [a] -> [a] -> [a]
++ String
" prime factor" String -> ShowS
forall a. [a] -> [a] -> [a]
++ (if Int
l Int -> Int -> Bool
forall a. Eq a => a -> a -> Bool
== Int
1 then String
"" else String
"s")) String -> ShowS
forall a. [a] -> [a] -> [a]
++
            String
": " String -> ShowS
forall a. [a] -> [a] -> [a]
++ String -> [String] -> String
forall a. [a] -> [[a]] -> [a]
List.intercalate String
" * "
                      (((Integer, Integer) -> String) -> [(Integer, Integer)] -> [String]
forall a b. (a -> b) -> [a] -> [b]
map (Term -> String
Term.toString (Term -> String)
-> ((Integer, Integer) -> Term) -> (Integer, Integer) -> String
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Integer, Integer) -> Term
Term.fromPrimePower) [(Integer, Integer)]
pks))
    ([(Integer, Integer)]
pks',r
r') <- IntegerFactorer r -> IntegerFactorer r
forall r. RandomGen r => IntegerFactorer r -> IntegerFactorer r
powerFactorInteger IntegerFactorer r
forall r. RandomGen r => IntegerFactorer r
ecmFactorInteger Config
cfg Integer
m r
r
    ([(Integer, Integer)], r) -> Verbose ([(Integer, Integer)], r)
forall (f :: * -> *) a. Applicative f => a -> f a
pure ([(Integer, Integer)]
pks [(Integer, Integer)]
-> [(Integer, Integer)] -> [(Integer, Integer)]
forall a. [a] -> [a] -> [a]
++ [(Integer, Integer)]
pks', r
r')

-------------------------------------------------------------------------------
-- Factoring polynomials over the integers
-------------------------------------------------------------------------------

factorZx :: Zx -> [(Zx,Integer)]
factorZx :: Zx -> [(Zx, Integer)]
factorZx Zx
f | Zx -> Bool
Zx.isConstant Zx
f = [(Zx
f,Integer
1)]
factorZx Zx
f = if Integer
n Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 then [(Zx, Integer)]
hks else (Integer -> Zx
Zx.constant Integer
n, Integer
1) (Zx, Integer) -> [(Zx, Integer)] -> [(Zx, Integer)]
forall a. a -> [a] -> [a]
: [(Zx, Integer)]
hks
  where
    (Integer
c,[(Zx, Integer)]
gks) = Zx -> (Integer, [(Zx, Integer)])
Bz.factor Zx
f
    ([(Zx, Integer)]
mks,[(Zx, Integer)]
hks) = ((Zx, Integer) -> Bool)
-> [(Zx, Integer)] -> ([(Zx, Integer)], [(Zx, Integer)])
forall a. (a -> Bool) -> [a] -> ([a], [a])
List.partition (Zx -> Bool
Zx.isConstant (Zx -> Bool) -> ((Zx, Integer) -> Zx) -> (Zx, Integer) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Zx, Integer) -> Zx
forall a b. (a, b) -> a
fst) [(Zx, Integer)]
gks
    n :: Integer
n = ((Zx, Integer) -> Integer -> Integer)
-> Integer -> [(Zx, Integer)] -> Integer
forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
List.foldr (\(Zx
m,Integer
k) Integer
z -> (Zx -> Integer
Zx.constantCoeff Zx
m Integer -> Integer -> Integer
forall a b. (Num a, Integral b) => a -> b -> a
^ Integer
k) Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Integer
z) Integer
c [(Zx, Integer)]
mks

-------------------------------------------------------------------------------
-- Factoring polynomials over GF(p)
-------------------------------------------------------------------------------

factorGfpx :: RandomGen r => Prime -> Gfpx -> r -> ([(Gfpx,Integer)],r)
factorGfpx :: Integer -> Gfpx -> r -> ([(Gfpx, Integer)], r)
factorGfpx Integer
_ Gfpx
f r
r | Gfpx -> Bool
Gfpx.isConstant Gfpx
f = ([(Gfpx
f,Integer
1)],r
r)
factorGfpx Integer
p Gfpx
f r
r = (if Integer
c Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
1 then [(Gfpx, Integer)]
hs else (Integer -> Gfpx
Gfpx.constant Integer
c, Integer
1) (Gfpx, Integer) -> [(Gfpx, Integer)] -> [(Gfpx, Integer)]
forall a. a -> [a] -> [a]
: [(Gfpx, Integer)]
hs, r
r')
  where
    ([(Gfpx, Integer)]
hs,r
r') = Integer -> Gfpx -> r -> ([(Gfpx, Integer)], r)
forall r.
RandomGen r =>
Integer -> Gfpx -> r -> ([(Gfpx, Integer)], r)
Gfpx.factorMonic Integer
p Gfpx
g r
r
    (Integer
c,Gfpx
g) = Integer -> Gfpx -> (Integer, Gfpx)
Gfpx.constMonic Integer
p Gfpx
f

-------------------------------------------------------------------------------
-- Factoring expression values
-------------------------------------------------------------------------------

factorValue :: RandomGen r => Config -> Value -> r -> Verbose (Term,r)
factorValue :: Config -> Value -> r -> Verbose (Term, r)
factorValue Config
cfg (ZValue Integer
n) r
r = do
    ([(Integer, Integer)]
pks,r
r') <- IntegerFactorer r
forall r. RandomGen r => IntegerFactorer r
factorInteger Config
cfg Integer
n r
r
    Term
t <- Term -> Verbose Term
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Term -> Verbose Term) -> Term -> Verbose Term
forall a b. (a -> b) -> a -> b
$ [(Integer, Integer)] -> Term
Term.fromPrimePowers [(Integer, Integer)]
pks
    (Term, r) -> Verbose (Term, r)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Term
t,r
r')
factorValue Config
_ (ZxValue Zx
f String
x) r
r = (Term, r) -> Verbose (Term, r)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Term
t,r
r)
  where
    gks :: [(Zx, Integer)]
gks = Zx -> [(Zx, Integer)]
factorZx Zx
f
    t :: Term
t = Term -> Term
Term.simplify (Term -> Term) -> Term -> Term
forall a b. (a -> b) -> a -> b
$ [Term] -> Term
Term.mkProduct ([Term] -> Term) -> [Term] -> Term
forall a b. (a -> b) -> a -> b
$
        ((Zx, Integer) -> Term) -> [(Zx, Integer)] -> [Term]
forall a b. (a -> b) -> [a] -> [b]
map (\(Zx
g,Integer
k) -> Term -> Term -> Term
ExpTerm (String -> Zx -> Term
Zx.toTerm String
x Zx
g) (Integer -> Term
IntegerTerm Integer
k)) [(Zx, Integer)]
gks
factorValue Config
_ (GfpValue Integer
p Integer
a) r
r = (Term, r) -> Verbose (Term, r)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Integer -> Integer -> Term
Term.fromGfp Integer
p Integer
a, r
r)
factorValue Config
_ (GfpxValue Integer
p Gfpx
f String
x) r
r = (Term, r) -> Verbose (Term, r)
forall (f :: * -> *) a. Applicative f => a -> f a
pure (Term
t,r
r')
  where
    ([(Gfpx, Integer)]
gks,r
r') = Integer -> Gfpx -> r -> ([(Gfpx, Integer)], r)
forall r.
RandomGen r =>
Integer -> Gfpx -> r -> ([(Gfpx, Integer)], r)
factorGfpx Integer
p Gfpx
f r
r
    t :: Term
t = (Term -> Integer -> Term) -> Integer -> Term -> Term
forall a b c. (a -> b -> c) -> b -> a -> c
flip Term -> Integer -> Term
Term.modulo Integer
p (Term -> Term) -> Term -> Term
forall a b. (a -> b) -> a -> b
$ Term -> Term
Term.simplify (Term -> Term) -> Term -> Term
forall a b. (a -> b) -> a -> b
$ [Term] -> Term
Term.mkProduct ([Term] -> Term) -> [Term] -> Term
forall a b. (a -> b) -> a -> b
$
        ((Gfpx, Integer) -> Term) -> [(Gfpx, Integer)] -> [Term]
forall a b. (a -> b) -> [a] -> [b]
map (\(Gfpx
g,Integer
k) -> Term -> Term -> Term
ExpTerm (Integer -> String -> Gfpx -> Term
Gfpx.polyToTerm Integer
p String
x Gfpx
g) (Integer -> Term
IntegerTerm Integer
k)) [(Gfpx, Integer)]
gks

{-
let cfg = defaultConfig
let n = 4
r <- System.Random.getStdGen
factorInteger cfg n r
powerFactorInteger ecmFactorInteger cfg n r
-}