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.