Portability | Non-portable (GHC extensions) |
---|---|

Stability | Provisional |

Maintainer | Daniel Fischer <daniel.is.fischer@googlemail.com> |

Safe Haskell | Safe-Infered |

Primality tests.

- isPrime :: Integer -> Bool
- isCertifiedPrime :: Integer -> Bool
- bailliePSW :: Integer -> Bool
- millerRabinV :: Int -> Integer -> Bool
- isStrongFermatPP :: Integer -> Integer -> Bool
- isFermatPP :: Integer -> Integer -> Bool
- data FactorSieve
- fsIsPrime :: FactorSieve -> Integer -> Bool
- trialDivisionPrimeTo :: Integer -> Integer -> Bool

# Standard tests

isPrime :: Integer -> BoolSource

tests whether `isPrime`

n`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 -> BoolSource

tests primality of `isCertifiedPrime`

n`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 -> BoolSource

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 -> BoolSource

A Miller-Rabin like probabilistic primality test with preceding
trial division. While the classic Miller-Rabin test uses
randomly chosen bases,

uses the `millerRabinV`

k n`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 -> BoolSource

tests whether `isStrongFermatPP`

n b`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

holds for all `isStrongFermatPP`

n b`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 `

for
all `mod`

n`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 `

and
the strong Fermat condition is reached at the same step for `mod`

4 == 1`a`

as for `b`

,
so primes are the most powerful bases to test.

isFermatPP :: Integer -> Integer -> BoolSource

tests whether `isFermatPP`

n b`n`

is a Fermat probable prime
for the base `b`

, that is, whether `b^(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 `mod`

n == 1

apply
with the modification that if `isStrongFermatPP`

`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 Source

A compact store of smallest prime factors.

fsIsPrime :: FactorSieve -> Integer -> BoolSource

Test primality using a `FactorSieve`

. If `n`

is out of bounds
of the sieve, fall back to `isPrime`

.

# Trial division

trialDivisionPrimeTo :: Integer -> Integer -> BoolSource

tests whether `trialDivisionPrimeTo`

bound n`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.