arithmoi-0.6.0.1: Efficient basic number-theoretic functions.

Copyright (c) 2011 Daniel Fischer MIT Daniel Fischer Provisional Non-portable (GHC extensions) None Haskell2010

Math.NumberTheory.Primes.Testing

Description

Primality tests.

Synopsis

# Standard tests

isPrime n tests whether n is a prime (negative or positive). It is a combination of trial division and Baillie-PSW test.

If isPrime n returns False then n is definitely composite. There is a theoretical possibility that isPrime n is True, but in fact n is not prime. However, no such numbers are known and none exist below 2^64. If you have found one, please report it, because it is a major discovery.

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

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.

Miller-Rabin probabilistic primality test. It consists of the trial division test and several rounds of the strong Fermat test with different bases. The choice of trial divisors and bases are implementation details and may change in future silently.

First argument stands for the number of rounds of strong Fermat test. If it is 0, only trial division test is performed.

If millerRabinV k n returns False then n is definitely composite. Otherwise n may appear composite with probability 1/4^k.

isStrongFermatPP n b tests whether non-negative n is a strong Fermat probable prime for base b.

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.

Please consult Deterministic variants of the Miller-Rabin primality test for the best choice of bases.

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

A compact store of smallest prime factors.

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

# Trial division

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.