Miller–Rabin primality test

The Miller - Rabin test or Miller - Selfridge - Rabin test is an algorithm from the mathematical branch number theory, in particular the algorithmic number theory.

He is a probabilistic primality test, but for which there are deterministic variants. Receives the probabilistic test is a natural number as input, it outputs either " is not prime " or " probably prime " from, the result is dependent on and to chance. He belongs to the class of Monte Carlo algorithms.

The Miller - Rabin test is named after Gary L. Miller and Michael O. Rabin. John L. Selfridge has used this test in 1974 before Rabin published it in 1976. Hence the alternative name Miller - Selfridge - Rabin test.

The Miller - Rabin test is similar to the Solovay -Strassen test, but this is superior in all aspects. It is faster, its probability of error is lower and any number that identifies the Solovay -Strassen test as composed, also has the Miller - Rabin test as a composite number.

Algorithm

Let n be an odd number of which is to be determined whether it is prime or not. First, select a random one base from the numbers 2, 3, ..., n - 1

The next step utilizes a test that consist only primes and strong pseudoprimes (base A). Namely, if we write

With odd d, it shall, if n is prime:

Or

For some r with 0 ≤ r < j. The derivation of these congruences is to find strong pseudo-prime in the next section and in the article. This condition is, however, occasionally met ( to each base a) and composite numbers. These hot strong pseudo prime numbers to base a

Operation

The Miller - Rabin test is calculated modulo the sequence

With. Each element of the result is in this case the square of its predecessor.

Is a prime number, then applies to the little Fermat theorem

And calculated by the Miller - Rabin test result therefore has the form

The only figures with

Are the numbers 1 and -1, as the following evidence shows, for a prime number.

For this reason, is the predecessor of a 1 in the result always a 1 or a -1. This means that for a prime number, the result of the Miller - Rabin test, either or, where the question mark for any numbers available.

Is an arbitrary number and does not start as calculated by the Miller -Rabin test sequence 1 and also does not contain -1, can not be prime. However, there are composite numbers, where the sequence begins with a base of a, 1 or contains a -1. These are the already mentioned strong pseudoprimes base a

Reliability

If n ≥ 3 is odd and not prime, contains the set { 2,3, ..., n -2 } at most elements with gcd (a, n) = 1, which are no witnesses to the compositeness. ( If gcd (a, n)> 1, or for any, then, of course, is immediately recognized as non- prime).

Is a compound where odd and one randomly selects one, it is thus likely that is not recognized as so assembled is smaller than. If you repeat the test several times for different from this amount, the probability decreases further. After steps is the probability of holding a composite number for primary, less than, say, for example, after four steps is less than 0.4 % and less than ten steps.

Deterministic variants

The Miller -Rabin algorithm can be applied deterministically by all bases are tested in a certain amount (example: if n < 9,080,191, then it is enough to test a = 31 and 73, see below).

If the tested is composed, to prime strong pseudo prime numbers are contained in a true subset of. This means that during testing all of an amount which produces, is one of a witness for the Zusammengesetztsein of. If it is assumed that the Riemann Hypothesis is true, then it follows that the group ( (log n ) 2) is generated by its elements smaller O what has already been led by Miller. The constant in the Landau notation was reduced by Eric Bach on 2. Therefore we obtain a deterministic primality test should all be tested. The running time of this algorithm is O ( (log n ) 4).

If the number n is small, it is not necessary to test all of the A <2 ( ln n ) 2, as it is known that a much smaller number is sufficient. For example, Pomerance, Selfridge and Wagstaff and Jaeschke have verified the following:

• When n < 1373653, it is sufficient to test a = 2 and 3,
• When n < 9080191, it is sufficient to test a = 31 and 73,
• When n < 4759123141, it is sufficient a = 2, 7, and test 61,
• When n < 2,152,302,898,747, it is sufficient a = 2, 3, 5, 7, and test 11,
• When n < 3,474,749,660,383, it is sufficient a = 2, 3, 5, 7, 11, and test 13,
• When n < 341,550,071,728,321, it is sufficient a = 2, 3, 5, 7, 11, 13, and test 17 ​​.

See also the Prime Pages, Miller -Rabin SPRP bases records, Zhang / Tang and also the sequence A014233 in OEIS to other criteria of a similar nature in this way you have a very fast deterministic primality tests for numbers in the appropriate field and rely on unproven assumptions need.

Practical Relevance

Primality tests are needed especially in cryptography. A typical example is the key generation for the RSA cryptosystem can be several large prime numbers are needed. While it was in 2002 with the AKS primality test for the first time, a provably deterministic, presented in polynomial time primality test running. However, its running time for practical applications usually too high, so for cryptographic software usually still the Miller -Rabin test is used. While it is theoretically possible that a compound is used as a prime number, however, the probability is so low that it does not matter in practice.