Math.NumberTheory.Primes.Testing

Primality tests.

Standard tests

isPrime :: Integer -> Bool

isPrime n tests whether n is a prime (negative or positive). First, trial division by the primes less than 1200 is performed. If that hasn't determined primality or compositeness, a Baillie PSW test is performed.

Since the Baillie PSW test may not be perfect, it is possible that some large composites are wrongly deemed prime, however, no composites passing the test are known and none exist below 2^64.

isCertifiedPrime :: Integer -> Bool

isCertifiedPrime n tests primality of n, first trial division by small primes is performed, then a Baillie PSW test and finally a prime certificate is constructed and verified, provided no step before found n to be composite. Constructing prime certificates can take a very long time, so use this with care.

Partial tests

bailliePSW :: Integer -> Bool

Primality test after Baillie, Pomerance, Selfridge and Wagstaff. The Baillie PSW test consists of a strong Fermat probable primality test followed by a (strong) Lucas primality test. This implementation assumes that the number n to test is odd and larger than 3. Even and small numbers have to be handled before. Also, before applying this test, trial division by small primes should be performed to identify many composites cheaply (although the Baillie PSW test is rather fast, about the same speed as a strong Fermat test for four or five bases usually, it is, for large numbers, much more costly than trial division by small primes, the primes less than 1000, say, so eliminating numbers with small prime factors beforehand is more efficient).

The Baillie PSW test is very reliable, so far no composite numbers passing it are known, and it is known (Gilchrist 2010) that no Baillie PSW pseudoprimes exist below 2^64. However, a heuristic argument by Pomerance indicates that there are likely infinitely many Baillie PSW pseudoprimes. On the other hand, according to http://mathworld.wolfram.com/Baillie-PSWPrimalityTest.html there is reason to believe that there are none with less than several thousand digits, so that for most use cases the test can be considered definitive.

millerRabinV :: Int -> Integer -> Bool

A Miller-Rabin like probabilistic primality test with preceding trial division. While the classic Miller-Rabin test uses randomly chosen bases, millerRabinV k n uses the k smallest primes as bases if trial division has not reached a conclusive result. (Only the primes up to 1200 are available in this module, so the maximal effective k is 196.)

isStrongFermatPP :: Integer -> Integer -> Bool

isStrongFermatPP n b tests whether n is a strong Fermat probable prime for base b, where n > 2 and 1 < b < n. The conditions on the arguments are not checked.

Apart from primes, also some composite numbers have the tested property, but those are rare. Very rare are composite numbers having the property for many bases, so testing a large prime candidate with several bases can identify composite numbers with high probability. An odd number n > 3 is prime if and only if isStrongFermatPP n b holds for all b with 2 <= b <= (n-1)/2, but of course checking all those bases would be less efficient than trial division, so one normally checks only a relatively small number of bases, depending on the desired degree of certainty. The probability that a randomly chosen base doesn't identify a composite number n is less than 1/4, so five to ten tests give a reasonable level of certainty in general.

Some notes about the choice of bases: b is a strong Fermat base for n if and only if n-b is, hence one needs only test b <= (n-1)/2. If b is a strong Fermat base for n, then so is b^k mod n for all k > 1, hence one needs not test perfect powers, since their base yields a stronger condition. Finally, if a and b are strong Fermat bases for n, then a*b is in most cases a strong Fermat base for n, it can only fail to be so if n mod 4 == 1 and the strong Fermat condition is reached at the same step for a as for b, so primes are the most powerful bases to test.

isFermatPP :: Integer -> Integer -> Bool

isFermatPP n b tests whether n is a Fermat probable prime for the base b, that is, whether b^(n-1) mod n == 1. This is a weaker but simpler condition. However, more is lost in strength than is gained in simplicity, so for primality testing, the strong check should be used. The remarks about the choice of bases to test from isStrongFermatPP apply with the modification that if a and b are Fermat bases for n, then a*b always is a Fermat base for n too. A Charmichael number is a composite number n which is a Fermat probable prime for all bases b coprime to n. By the above, only primes p <= n/2 not dividing n need to be tested to identify Carmichael numbers (however, testing all those primes would be less efficient than determining Carmichaelness from the prime factorisation; but testing an appropriate number of prime bases is reasonable to find out whether it's worth the effort to undertake the prime factorisation).

Using a sieve

data FactorSieve

A compact store of smallest prime factors.

fsIsPrime :: FactorSieve -> Integer -> Bool

Test primality using a FactorSieve. If n is out of bounds of the sieve, fall back to isPrime.

Trial division

trialDivisionPrimeTo :: Integer -> Integer -> Bool

trialDivisionPrimeTo bound n tests whether n is coprime to all primes <= bound. If n <= bound^2, this is a full prime test, but very slow if n has no small prime divisors.