|Portability||Non-portable (GHC extensions)|
|Maintainer||Daniel Fischer <email@example.com>|
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
The tests in this module may wrongly consider some composite numbers as prime.
For the Baillie-PSW test, no pseudoprimes are known, and it is known that none
2^64, so for most practical purposes it can be regarded as conclusive.
Nevertheless, it is desirable to certify numbers passing it as primes (or find that
they are composite). The addition of prime certificates is planned for the next release.
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
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
A Miller-Rabin like probabilistic primality test with preceding
trial division. While the classic Miller-Rabin test uses
randomly chosen bases,
millerRabinV k n
smallest primes as bases if trial division has not reached
a conclusive result. (Only the primes up to
available in this module, so the maximal effective
isStrongFermatPP n b
n is a strong Fermat
probable prime for base
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
holds for all
isStrongFermatPP n b
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
Some notes about the choice of bases:
b is a strong Fermat base
n if and only if
n-b is, hence one needs only test
b <= (n-1)/2.
b is a strong Fermat base for
n, then so is
k > 1, hence one needs not test perfect powers, since their
base yields a stronger condition. Finally, if
b are strong
Fermat bases for
a*b is in most cases a strong Fermat
n, it can only fail to be so if
the strong Fermat condition is reached at the same step for
mod 4 == 1
a as for
so primes are the most powerful bases to test.
isFermatPP n b
n is a Fermat probable prime
for the base
b, that is, whether
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
mod n == 1
with the modification that if
b are Fermat bases
a*b always is a Fermat base for
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).