{-
	Copyright (C) 2011-2015 Dr. Alistair Ward

	This program is free software: you can redistribute it and/or modify
	it under the terms of the GNU General Public License as published by
	the Free Software Foundation, either version 3 of the License, or
	(at your option) any later version.

	This program is distributed in the hope that it will be useful,
	but WITHOUT ANY WARRANTY; without even the implied warranty of
	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
	GNU General Public License for more details.

	You should have received a copy of the GNU General Public License
	along with this program.  If not, see <https://www.gnu.org/licenses/>.
-}
{- |
 [@AUTHOR@]	Dr. Alistair Ward

 [@DESCRIPTION@]

	* Determines whether an integer is prime.

	* <https://en.wikipedia.org/wiki/Primality_test>.

	* <https://primes.utm.edu/index.html>

	* CAVEAT: it doesn't determine the prime-factors of composite numbers, just that they exist.
-}

module Factory.Math.Implementations.Primality(
-- * Types
-- ** Data-types
	Algorithm(..)
-- * Functions
-- ** Predicates
--	isPrimeByAKS,
--	isPrimeByMillerRabin,
--	witnessesCompositeness
) 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

-- | The algorithms by which /primality/-testing has been implemented.
data Algorithm factorisationAlgorithm
	= AKS factorisationAlgorithm	-- ^ <https://en.wikipedia.org/wiki/AKS_primality_test>.
	| MillerRabin			-- ^ <https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test>.
	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	-- The only even prime.
	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`)			-- The candidate has a small prime-factor, and is therefore composite.
			) ([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)				-- The candidate must be at least double the small prime, for it to be a potential factor.
			) ([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 {-arbitrarily-} ([i] -> Bool) -> [i] -> Bool
forall a b. (a -> b) -> a -> b
$ [i]
forall int. Integral int => [int]
Data.Numbers.Primes.primes	-- Excludes even numbers, provided at least the 1st prime is tested.
		)		= 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

{- |
	* An implementation of the /Agrawal-Kayal-Saxena/ primality-test; <https://en.wikipedia.org/wiki/AKS_primality_test>,
	using the /Lenstra/ and /Pomerance/ algorithm.

	* CAVEAT: this deterministic algorithm has a theoretical time-complexity of @O(log^6)@,
	and therefore can't compete with the performance of probabilistic ones.

	* The /formal polynomials/ used in this algorithm, are conceptually different from /polynomial functions/;
	the /indeterminate/ and its powers, are merely used to name a sequence of pigeon-holes in which /coefficients/ are stored,
	and is never substituted for a specific value.
	This mind-shift, allows one to introduce concepts like /modular/ arithmetic on polynomials,
	which merely represent an operation on their coefficients and the pigeon-hole in which they're placed.

	[@Manindra Agrawal, Neeraj Kayal and Nitin Saxena@]	<https://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf>.

	[@H. W. Lenstra, Jr. and Carl Pomerance@]		<https://www.math.dartmouth.edu/~carlp/PDF/complexity12.pdf>.

	[@Salembier and Southerington@]				<https://ece.gmu.edu/courses/ECE746/project/F06_Project_resources/Salembier_Southerington_AKS.pdf>,

	[@R. Crandall and J. Papadopoulos@]			<https://images.apple.com/acg/pdf/aks3.pdf>,

	[@Andreas Klappenecker@]				<https://faculty.cs.tamu.edu/klappi/629/aks.ps>,

	[@Vibhor Bhatt and G. K. Patra@]			<https://www.cmmacs.ernet.in/cmmacs/Publications/resch_rep/rrcm0307.pdf>,
-}
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	-- Step 1.
 ) 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]	-- Step 3.
 ) 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	{-Benefits from '+RTS -H100M', which reduces garbage-collections-} (
		\i
a	-> let
--			lhs, rhs :: Data.Polynomial.Polynomial i i
			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 {-power-} i
n {-modulus-}
			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
		) -- Because all these polynomials are /monic/, one can establish /congruence/ using /integer/-division.
	) [
		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
	] -- Step 4; (x + a)^n ~ x^n + a mod (x^r - 1, n).
 ) 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
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 ..]	-- Step 2.

--	modulus :: Data.Polynomial.Polynomial i i
	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)]

{- |
	* Uses the specified 'base' in an attempt to prove the /compositeness/ of an integer.

	* This is the opposite of the /Miller Test/; <https://mathworld.wolfram.com/MillersPrimalityTest.html>.

	* If the result is 'True', then the candidate is /composite/; regrettably the converse isn't true.
	Amongst the set of possible bases, over three-quarters are /witnesses/ to the compositeness of a /composite/ candidate,
	the remainder belong to the subset of /liars/.
	In consequence, many false results must be accumulated for different bases, to convincingly identify a prime.
-}
witnessesCompositeness :: (Integral i, Show i)
	=> i	-- ^ Candidate integer.
	-> i
	-> Int
	-> i	-- ^ Base.
	-> 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	-- Repeatedly modulo-square.
 ) [
	(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,					-- Check whether the zeroeth modulo-power is incongruent to one.
	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	-- Check whether any modulo-power is incongruent to -1.
 ]

{- |
	* Repeatedly calls 'witnessesCompositeness', to progressively increase the probability of detecting a /composite/ number,
	until ultimately the candidate integer is proven to be prime.

	* Should all bases be tested, then the test is deterministic, but at an efficiency /lower/ than performing prime-factorisation.

	* The test becomes deterministic, for any candidate integer, when the number of tests reaches the limit defined by /Eric Bach/.

	* A testing of smaller set of bases, is sufficient for candidates smaller than various thresholds; <https://primes.utm.edu/prove/prove2_3.html>.

	* <https://en.wikipedia.org/wiki/Miller-Rabin_primality_test>.

	* <https://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html>

	* <https://mathworld.wolfram.com/StrongPseudoprime.html>.

	* <https://oeis.org/A014233>, <https://oeis.org/A006945>.
-}
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	-- Odd-remainder.
 ) (
	[(i, i)] -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length [(i, i)]
binaryFactors	-- The number of times that 'two' can be factored-out from 'predecessor'.
 ) (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 {-drop the original-} ([(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)	-- Factor-out powers of two.
	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 {-Eric Bach-}) (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 {-avoid premature rounding-} (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 {-overflows at 10^851-})
		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),			-- All odd integers less this, are prime, and require no further verification.
				(Int
1,	i
2047),
				(Int
2,	i
1373653),
				(Int
3,	i
25326001),
				(Int
4,	i
3215031751),
				(Int
5,	i
2152302898747),		-- Jaeschke ...
				(Int
6,	i
3474749660383),
				(Int
8,	i
341550071728321),
				(Int
11,	i
3825123056546413051),	-- Zhang ...
				(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))	-- At least.
			 ]