Primality Test - Probabilistic Tests

Probabilistic Tests

Most popular primality tests are probabilistic tests. These tests use, apart from the tested number n, some other numbers a which are chosen at random from some sample space; the usual randomized primality tests never report a prime number as composite, but it is possible for a composite number to be reported as prime. The probability of error can be reduced by repeating the test with several independently chosen values of a; for two commonly used tests, for any composite n at least half the a's detect n's compositeness, so k repetitions reduce the error probability to at most 2−k, which can be made arbitrarily small by increasing k.

The basic structure of randomized primality tests is as follows:

1. Randomly pick a number a.
2. Check some equality (corresponding to the chosen test) involving a and the given number n. If the equality fails to hold true, then n is a composite number, a is known as a witness for the compositeness, and the test stops.
3. Repeat from step 1 until the required certainty is achieved.

After several iterations, if n is not found to be a composite number, then it can be declared probably prime.

The simplest probabilistic primality test is the Fermat primality test (actually a compositeness test). It works as follows:

Given an integer n, choose some integer a coprime to n and calculate an − 1 modulo n. If the result is different from 1, then n is composite. If it is 1, then n may or may not be prime.

The Fermat primality test is only a heuristic test; some composite numbers (Carmichael numbers) will be declared "probably prime" no matter what witness is chosen. Nevertheless, it is often used if a rapid screening of numbers is needed, for instance in the key generation phase of the RSA public key cryptographic algorithm.

The Miller–Rabin primality test and Solovay–Strassen primality test are more sophisticated variants which detect all composites (once again, this means: for every composite number n, at least 3/4 (Miller–Rabin) or 1/2 (Solovay–Strassen) of numbers a are witnesses of compositeness of n). These are also compositeness tests.

The Miller–Rabin primality test works as follows: Given an integer n, choose some integer a < n. Let 2sd = n − 1 where d is odd. If

and

for all

then n is composite and a is a witness for the compositeness. Otherwise, n may or may not be prime.

The Solovay–Strassen primality test uses another equality: Given an odd number n, choose some integer a < n, if

, where is the Jacobi symbol,

then n is composite and a is a witness for the compositeness. Otherwise, n may or may not be prime.

These two primality tests are often the methods of choice, as they are simple and much faster than other general primality tests. One method of improving efficiency further in some cases is the Frobenius pseudoprimality test; a round of this test takes about three times as long as a round of Miller–Rabin, but achieves a probability bound comparable to seven rounds of Miller–Rabin.

Leonard Adleman and Huang presented an errorless (but expected polynomial-time) variant of the elliptic curve primality test. Unlike the other probabilistic tests, this algorithm produces a primality certificate, and thus can be used to prove that a number is prime. The algorithm is prohibitively slow in practice.