Copyright | (c) 2011 Daniel Fischer |
---|---|

License | MIT |

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

Stability | Provisional |

Portability | Non-portable (GHC extensions) |

Safe Haskell | None |

Language | Haskell2010 |

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 -> Bool Source #

`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 :: Integer -> Bool Source #

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 -> Bool Source #

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

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 :: Integer -> Integer -> Bool Source #

tests whether non-negative `isStrongFermatPP`

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

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.

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

isFermatPP :: Integer -> Integer -> Bool Source #

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 -> Bool Source #

Test primality using a `FactorSieve`

. If `n`

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

.

# Trial division

trialDivisionPrimeTo :: Integer -> Integer -> Bool Source #

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.