#### 15.7.1 Prime Testing

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.