[ << ] | [ < ] | [ Up ] | [ > ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |

### 15.7.1 Prime Testing

The primality testing in `mpz_probab_prime_p`

(see section 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 section 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*.

This document was generated on *March 31, 2014* using *texi2html 5.0*.