Next: Factorial Algorithm, Previous: Other Algorithms, Up: Other Algorithms [Index]

The primality testing in `mpz_probab_prime_p`

(see Number Theoretic Functions) first does some trial division by small factors and then uses the
Miller-Rabin probabilistic primality testing algorithm, as described in Knuth
section 4.5.4 algorithm P (see References).

For an odd input *n*, and with *n = q*2^k+1* where
*q* is odd, this algorithm selects a random base *x* and tests
whether *x^q mod n* is 1 or *-1*, or an *x^(q*2^j) mod n* is *1*, for *1<=j<=k*. If so then *n*
is probably prime, if not then *n* is definitely composite.

Any prime *n* will pass the test, but some composites do too. Such
composites are known as strong pseudoprimes to base *x*. No *n* is
a strong pseudoprime to more than *1/4* of all bases (see Knuth exercise
22), hence with *x* chosen at random there’s no more than a *1/4*
chance a “probable prime” will in fact be composite.

In fact strong pseudoprimes are quite rare, making the test much more
powerful than this analysis would suggest, but *1/4* is all that’s proven
for an arbitrary *n*.