module Factory.Math.Implementations.Primality(
Algorithm(..)
) where
import Control.Arrow((&&&))
import qualified Control.DeepSeq
import qualified Control.Parallel.Strategies
import qualified Data.Default
import qualified Data.List
import qualified Data.Numbers.Primes
import qualified Factory.Data.MonicPolynomial as Data.MonicPolynomial
import qualified Factory.Data.Polynomial as Data.Polynomial
import qualified Factory.Data.QuotientRing as Data.QuotientRing
import qualified Factory.Math.MultiplicativeOrder as Math.MultiplicativeOrder
import qualified Factory.Math.PerfectPower as Math.PerfectPower
import qualified Factory.Math.Power as Math.Power
import qualified Factory.Math.Primality as Math.Primality
import qualified Factory.Math.PrimeFactorisation as Math.PrimeFactorisation
data Algorithm factorisationAlgorithm
= AKS factorisationAlgorithm
| MillerRabin
deriving (Algorithm factorisationAlgorithm
-> Algorithm factorisationAlgorithm -> Bool
(Algorithm factorisationAlgorithm
-> Algorithm factorisationAlgorithm -> Bool)
-> (Algorithm factorisationAlgorithm
-> Algorithm factorisationAlgorithm -> Bool)
-> Eq (Algorithm factorisationAlgorithm)
forall factorisationAlgorithm.
Eq factorisationAlgorithm =>
Algorithm factorisationAlgorithm
-> Algorithm factorisationAlgorithm -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
/= :: Algorithm factorisationAlgorithm
-> Algorithm factorisationAlgorithm -> Bool
$c/= :: forall factorisationAlgorithm.
Eq factorisationAlgorithm =>
Algorithm factorisationAlgorithm
-> Algorithm factorisationAlgorithm -> Bool
== :: Algorithm factorisationAlgorithm
-> Algorithm factorisationAlgorithm -> Bool
$c== :: forall factorisationAlgorithm.
Eq factorisationAlgorithm =>
Algorithm factorisationAlgorithm
-> Algorithm factorisationAlgorithm -> Bool
Eq, ReadPrec [Algorithm factorisationAlgorithm]
ReadPrec (Algorithm factorisationAlgorithm)
Int -> ReadS (Algorithm factorisationAlgorithm)
ReadS [Algorithm factorisationAlgorithm]
(Int -> ReadS (Algorithm factorisationAlgorithm))
-> ReadS [Algorithm factorisationAlgorithm]
-> ReadPrec (Algorithm factorisationAlgorithm)
-> ReadPrec [Algorithm factorisationAlgorithm]
-> Read (Algorithm factorisationAlgorithm)
forall factorisationAlgorithm.
Read factorisationAlgorithm =>
ReadPrec [Algorithm factorisationAlgorithm]
forall factorisationAlgorithm.
Read factorisationAlgorithm =>
ReadPrec (Algorithm factorisationAlgorithm)
forall factorisationAlgorithm.
Read factorisationAlgorithm =>
Int -> ReadS (Algorithm factorisationAlgorithm)
forall factorisationAlgorithm.
Read factorisationAlgorithm =>
ReadS [Algorithm factorisationAlgorithm]
forall a.
(Int -> ReadS a)
-> ReadS [a] -> ReadPrec a -> ReadPrec [a] -> Read a
readListPrec :: ReadPrec [Algorithm factorisationAlgorithm]
$creadListPrec :: forall factorisationAlgorithm.
Read factorisationAlgorithm =>
ReadPrec [Algorithm factorisationAlgorithm]
readPrec :: ReadPrec (Algorithm factorisationAlgorithm)
$creadPrec :: forall factorisationAlgorithm.
Read factorisationAlgorithm =>
ReadPrec (Algorithm factorisationAlgorithm)
readList :: ReadS [Algorithm factorisationAlgorithm]
$creadList :: forall factorisationAlgorithm.
Read factorisationAlgorithm =>
ReadS [Algorithm factorisationAlgorithm]
readsPrec :: Int -> ReadS (Algorithm factorisationAlgorithm)
$creadsPrec :: forall factorisationAlgorithm.
Read factorisationAlgorithm =>
Int -> ReadS (Algorithm factorisationAlgorithm)
Read, Int -> Algorithm factorisationAlgorithm -> ShowS
[Algorithm factorisationAlgorithm] -> ShowS
Algorithm factorisationAlgorithm -> String
(Int -> Algorithm factorisationAlgorithm -> ShowS)
-> (Algorithm factorisationAlgorithm -> String)
-> ([Algorithm factorisationAlgorithm] -> ShowS)
-> Show (Algorithm factorisationAlgorithm)
forall factorisationAlgorithm.
Show factorisationAlgorithm =>
Int -> Algorithm factorisationAlgorithm -> ShowS
forall factorisationAlgorithm.
Show factorisationAlgorithm =>
[Algorithm factorisationAlgorithm] -> ShowS
forall factorisationAlgorithm.
Show factorisationAlgorithm =>
Algorithm factorisationAlgorithm -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
showList :: [Algorithm factorisationAlgorithm] -> ShowS
$cshowList :: forall factorisationAlgorithm.
Show factorisationAlgorithm =>
[Algorithm factorisationAlgorithm] -> ShowS
show :: Algorithm factorisationAlgorithm -> String
$cshow :: forall factorisationAlgorithm.
Show factorisationAlgorithm =>
Algorithm factorisationAlgorithm -> String
showsPrec :: Int -> Algorithm factorisationAlgorithm -> ShowS
$cshowsPrec :: forall factorisationAlgorithm.
Show factorisationAlgorithm =>
Int -> Algorithm factorisationAlgorithm -> ShowS
Show)
instance Data.Default.Default (Algorithm factorisationAlgorithm) where
def :: Algorithm factorisationAlgorithm
def = Algorithm factorisationAlgorithm
forall factorisationAlgorithm. Algorithm factorisationAlgorithm
MillerRabin
instance Math.PrimeFactorisation.Algorithmic factorisationAlgorithm => Math.Primality.Algorithmic (Algorithm factorisationAlgorithm) where
isPrime :: Algorithm factorisationAlgorithm -> i -> Bool
isPrime Algorithm factorisationAlgorithm
_ i
2 = Bool
True
isPrime Algorithm factorisationAlgorithm
algorithm i
candidate
| i
candidate i -> i -> Bool
forall a. Ord a => a -> a -> Bool
< i
2 Bool -> Bool -> Bool
|| (
(i -> Bool) -> [i] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (
(i -> i -> Bool
forall a. Eq a => a -> a -> Bool
== i
0) (i -> Bool) -> (i -> i) -> i -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (i
candidate i -> i -> i
forall a. Integral a => a -> a -> a
`rem`)
) ([i] -> Bool) -> ([i] -> [i]) -> [i] -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (i -> Bool) -> [i] -> [i]
forall a. (a -> Bool) -> [a] -> [a]
filter (
(i
candidate i -> i -> Bool
forall a. Ord a => a -> a -> Bool
>=) (i -> Bool) -> (i -> i) -> i -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (i -> i -> i
forall a. Num a => a -> a -> a
* i
2)
) ([i] -> [i]) -> ([i] -> [i]) -> [i] -> [i]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> [i] -> [i]
forall a. Int -> [a] -> [a]
take Int
5 ([i] -> Bool) -> [i] -> Bool
forall a b. (a -> b) -> a -> b
$ [i]
forall int. Integral int => [int]
Data.Numbers.Primes.primes
) = Bool
False
| Bool
otherwise = (
case Algorithm factorisationAlgorithm
algorithm of
AKS factorisationAlgorithm
factorisationAlgorithm -> factorisationAlgorithm -> i -> Bool
forall i factorisationAlgorithm.
(NFData i, Integral i, Algorithmic factorisationAlgorithm,
Show i) =>
factorisationAlgorithm -> i -> Bool
isPrimeByAKS factorisationAlgorithm
factorisationAlgorithm
Algorithm factorisationAlgorithm
MillerRabin -> i -> Bool
forall i. (Integral i, Show i) => i -> Bool
isPrimeByMillerRabin
) i
candidate
isPrimeByAKS :: (
Control.DeepSeq.NFData i,
Integral i,
Math.PrimeFactorisation.Algorithmic factorisationAlgorithm,
Show i
) => factorisationAlgorithm -> i -> Bool
isPrimeByAKS :: factorisationAlgorithm -> i -> Bool
isPrimeByAKS factorisationAlgorithm
factorisationAlgorithm i
n = Bool -> Bool
not (
i -> Bool
forall i. Integral i => i -> Bool
Math.PerfectPower.isPerfectPower i
n
) Bool -> Bool -> Bool
&& (
i -> i -> Bool
forall i. Integral i => i -> i -> Bool
Math.Primality.areCoprime i
n (i -> Bool) -> [i] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
`all` i -> [i] -> [i]
forall a. Eq a => a -> [a] -> [a]
Data.List.delete i
n [i
2 .. i
r]
) Bool -> Bool -> Bool
&& [Bool] -> Bool
forall (t :: * -> *). Foldable t => t Bool -> Bool
and (
Strategy Bool -> (i -> Bool) -> [i] -> [Bool]
forall b a. Strategy b -> (a -> b) -> [a] -> [b]
Control.Parallel.Strategies.parMap Strategy Bool
forall a. NFData a => Strategy a
Control.Parallel.Strategies.rdeepseq (
\i
a -> let
lhs :: Polynomial i i
lhs = Polynomial i i -> i -> i -> Polynomial i i
forall c power e.
(Integral c, Integral power, Num e, Ord e, Show power) =>
Polynomial c e -> power -> c -> Polynomial c e
Data.Polynomial.raiseModulo (i -> i -> Polynomial i i
forall c e. (Eq c, Num c, Num e) => c -> c -> Polynomial c e
Data.Polynomial.mkLinear i
1 i
a) i
n i
n
rhs :: Polynomial i i
rhs = Polynomial i i -> i -> Polynomial i i
forall c e. Integral c => Polynomial c e -> c -> Polynomial c e
Data.Polynomial.mod' (MonomialList i i -> Polynomial i i
forall c e.
(Eq c, Num c, Ord e) =>
MonomialList c e -> Polynomial c e
Data.Polynomial.mkPolynomial [(i
1, i
n), (i
a, i
0)]) i
n
in MonicPolynomial i i
-> MonicPolynomial i i -> MonicPolynomial i i -> Bool
forall q. (Eq q, QuotientRing q) => q -> q -> q -> Bool
Data.QuotientRing.areCongruentModulo (
Polynomial i i -> MonicPolynomial i i
forall c e.
(Eq c, Num c, Show c, Show e) =>
Polynomial c e -> MonicPolynomial c e
Data.MonicPolynomial.mkMonicPolynomial Polynomial i i
lhs
) (
Polynomial i i -> MonicPolynomial i i
forall c e.
(Eq c, Num c, Show c, Show e) =>
Polynomial c e -> MonicPolynomial c e
Data.MonicPolynomial.mkMonicPolynomial Polynomial i i
rhs
) (
Polynomial i i -> MonicPolynomial i i
forall c e.
(Eq c, Num c, Show c, Show e) =>
Polynomial c e -> MonicPolynomial c e
Data.MonicPolynomial.mkMonicPolynomial Polynomial i i
modulus
)
) [
i
1 .. Double -> i
forall a b. (RealFrac a, Integral b) => a -> b
floor (Double -> i) -> (Double -> Double) -> Double -> i
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Double -> Double -> Double
forall a. Num a => a -> a -> a
* Double
lg) (Double -> Double) -> (Double -> Double) -> Double -> Double
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Double -> Double
forall a. Floating a => a -> a
sqrt (Double -> i) -> Double -> i
forall a b. (a -> b) -> a -> b
$ i -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral i
r
]
) where
lg :: Double
lg :: Double
lg = Double -> Double -> Double
forall a. Floating a => a -> a -> a
logBase Double
2 (Double -> Double) -> Double -> Double
forall a b. (a -> b) -> a -> b
$ i -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral i
n
r :: i
r = (i, i) -> i
forall a b. (a, b) -> a
fst ((i, i) -> i) -> ([i] -> (i, i)) -> [i] -> i
forall b c a. (b -> c) -> (a -> b) -> a -> c
. MonomialList i i -> (i, i)
forall a. [a] -> a
head (MonomialList i i -> (i, i))
-> ([i] -> MonomialList i i) -> [i] -> (i, i)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((i, i) -> Bool) -> MonomialList i i -> MonomialList i i
forall a. (a -> Bool) -> [a] -> [a]
dropWhile (
(i -> i -> Bool
forall a. Ord a => a -> a -> Bool
<= Double -> i
forall a b. (RealFrac a, Integral b) => a -> b
floor (Double -> Double
forall n. Num n => n -> n
Math.Power.square Double
lg)) (i -> Bool) -> ((i, i) -> i) -> (i, i) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (i, i) -> i
forall a b. (a, b) -> b
snd
) (MonomialList i i -> MonomialList i i)
-> ([i] -> MonomialList i i) -> [i] -> MonomialList i i
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (i -> (i, i)) -> [i] -> MonomialList i i
forall a b. (a -> b) -> [a] -> [b]
map (
i -> i
forall a. a -> a
id (i -> i) -> (i -> i) -> i -> (i, i)
forall (a :: * -> * -> *) b c c'.
Arrow a =>
a b c -> a b c' -> a b (c, c')
&&& factorisationAlgorithm -> i -> i -> i
forall primeFactorisationAlgorithm i.
(Algorithmic primeFactorisationAlgorithm, NFData i, Integral i,
Show i) =>
primeFactorisationAlgorithm -> i -> i -> i
Math.MultiplicativeOrder.multiplicativeOrder factorisationAlgorithm
factorisationAlgorithm i
n
) ([i] -> i) -> [i] -> i
forall a b. (a -> b) -> a -> b
$ i -> i -> Bool
forall i. Integral i => i -> i -> Bool
Math.Primality.areCoprime i
n (i -> Bool) -> [i] -> [i]
forall a. (a -> Bool) -> [a] -> [a]
`filter` [i
2 ..]
modulus :: Polynomial i i
modulus = MonomialList i i -> Polynomial i i
forall c e.
(Eq c, Num c, Ord e) =>
MonomialList c e -> Polynomial c e
Data.Polynomial.mkPolynomial [(i
1, i
r), (i -> i
forall n. Num n => n -> n
negate i
1, i
0)]
witnessesCompositeness :: (Integral i, Show i)
=> i
-> i
-> Int
-> i
-> Bool
witnessesCompositeness :: i -> i -> Int -> i -> Bool
witnessesCompositeness i
candidate i
oddRemainder Int
nPowersOfTwo i
base = (([i] -> Bool) -> Bool) -> [[i] -> Bool] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (
([i] -> Bool) -> [i] -> Bool
forall a b. (a -> b) -> a -> b
$ ((i -> i -> i
forall a. Integral a => a -> a -> a
`rem` i
candidate) (i -> i) -> (i -> i) -> i -> i
forall b c a. (b -> c) -> (a -> b) -> a -> c
. i -> i
forall n. Num n => n -> n
Math.Power.square) (i -> i) -> i -> [i]
forall a. (a -> a) -> a -> [a]
`iterate` i -> i -> i -> i
forall i power.
(Integral i, Integral power, Show power) =>
i -> power -> i -> i
Math.Power.raiseModulo i
base i
oddRemainder i
candidate
) [
(i -> i -> Bool
forall a. Eq a => a -> a -> Bool
/= i
1) (i -> Bool) -> ([i] -> i) -> [i] -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [i] -> i
forall a. [a] -> a
head,
i -> [i] -> Bool
forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
notElem (i -> i
forall a. Enum a => a -> a
pred i
candidate) ([i] -> Bool) -> ([i] -> [i]) -> [i] -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Int -> [i] -> [i]
forall a. Int -> [a] -> [a]
take Int
nPowersOfTwo
]
isPrimeByMillerRabin :: (Integral i, Show i) => i -> Bool
isPrimeByMillerRabin :: i -> Bool
isPrimeByMillerRabin i
primeCandidate = Bool -> Bool
not (Bool -> Bool) -> Bool -> Bool
forall a b. (a -> b) -> a -> b
$ i -> i -> Int -> i -> Bool
forall i. (Integral i, Show i) => i -> i -> Int -> i -> Bool
witnessesCompositeness i
primeCandidate (
(i, i) -> i
forall a b. (a, b) -> a
fst ((i, i) -> i) -> (i, i) -> i
forall a b. (a -> b) -> a -> b
$ [(i, i)] -> (i, i)
forall a. [a] -> a
last [(i, i)]
binaryFactors
) (
[(i, i)] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [(i, i)]
binaryFactors
) (i -> Bool) -> [i] -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
`any` [i]
testBases where
predecessor :: i
predecessor = i -> i
forall a. Enum a => a -> a
pred i
primeCandidate
binaryFactors :: [(i, i)]
binaryFactors = ((i, i) -> Bool) -> [(i, i)] -> [(i, i)]
forall a. (a -> Bool) -> [a] -> [a]
takeWhile ((i -> i -> Bool
forall a. Eq a => a -> a -> Bool
== i
0) (i -> Bool) -> ((i, i) -> i) -> (i, i) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (i, i) -> i
forall a b. (a, b) -> b
snd) ([(i, i)] -> [(i, i)])
-> ([(i, i)] -> [(i, i)]) -> [(i, i)] -> [(i, i)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [(i, i)] -> [(i, i)]
forall a. [a] -> [a]
tail ([(i, i)] -> [(i, i)]) -> [(i, i)] -> [(i, i)]
forall a b. (a -> b) -> a -> b
$ ((i, i) -> (i, i)) -> (i, i) -> [(i, i)]
forall a. (a -> a) -> a -> [a]
iterate ((i -> i -> (i, i)
forall a. Integral a => a -> a -> (a, a)
`quotRem` i
2) (i -> (i, i)) -> ((i, i) -> i) -> (i, i) -> (i, i)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (i, i) -> i
forall a b. (a, b) -> a
fst) (i
predecessor, i
0)
testBases :: [i]
testBases
| [Int] -> Bool
forall (t :: * -> *) a. Foldable t => t a -> Bool
null [Int]
fewestPrimeBases = let
millersTestSet :: i
millersTestSet = Rational -> i
forall a b. (RealFrac a, Integral b) => a -> b
floor (Rational -> i) -> (Double -> Rational) -> Double -> i
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Rational -> Rational -> Rational
forall a. Num a => a -> a -> a
* Rational
2 ) (Rational -> Rational)
-> (Double -> Rational) -> Double -> Rational
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Rational -> Rational
forall n. Num n => n -> n
Math.Power.square (Rational -> Rational)
-> (Double -> Rational) -> Double -> Rational
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Double -> Rational
forall a. Real a => a -> Rational
toRational (Double -> i) -> Double -> i
forall a b. (a -> b) -> a -> b
$ Double -> Double
forall a. Floating a => a -> a
log (i -> Double
forall a b. (Integral a, Num b) => a -> b
fromIntegral i
primeCandidate :: Double )
in [i
2 .. i
predecessor i -> i -> i
forall a. Ord a => a -> a -> a
`min` i
millersTestSet]
| Bool
otherwise = [Int] -> Int
forall a. [a] -> a
head [Int]
fewestPrimeBases Int -> [i] -> [i]
forall a. Int -> [a] -> [a]
`take` [i]
forall int. Integral int => [int]
Data.Numbers.Primes.primes
where
fewestPrimeBases :: [Int]
fewestPrimeBases = ((Int, i) -> Int) -> [(Int, i)] -> [Int]
forall a b. (a -> b) -> [a] -> [b]
map (Int, i) -> Int
forall a b. (a, b) -> a
fst ([(Int, i)] -> [Int]) -> [(Int, i)] -> [Int]
forall a b. (a -> b) -> a -> b
$ ((Int, i) -> Bool) -> [(Int, i)] -> [(Int, i)]
forall a. (a -> Bool) -> [a] -> [a]
dropWhile ((i
primeCandidate i -> i -> Bool
forall a. Ord a => a -> a -> Bool
>=) (i -> Bool) -> ((Int, i) -> i) -> (Int, i) -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (Int, i) -> i
forall a b. (a, b) -> b
snd) [
(Int
0, i
9),
(Int
1, i
2047),
(Int
2, i
1373653),
(Int
3, i
25326001),
(Int
4, i
3215031751),
(Int
5, i
2152302898747),
(Int
6, i
3474749660383),
(Int
8, i
341550071728321),
(Int
11, i
3825123056546413051),
(Int
12, i
318665857834031151167461),
(Int
13, i
3317044064679887385961981),
(Int
14, i
6003094289670105800312596501),
(Int
15, i
59276361075595573263446330101),
(Int
17, i
564132928021909221014087501701),
(Int
19, i
1543267864443420616877677640751301),
(Int
20, i
10 i -> Int -> i
forall a b. (Num a, Integral b) => a -> b -> a
^ (Int
36 :: Int))
]