Miller-Rabin test

The Miller-Rabin test or Miller-Selfridge-Rabin test (MRT for short) is a probabilistic prime number test and thus an algorithm from the mathematical subfield of number theory , in particular algorithmic number theory .

The MRT receives an odd natural number as input , of which one wants to know whether it is prime, and another number and outputs either “composite” or “probably prime”. If prime, the output is always “probably prime”. Otherwise, in most cases, "composed" is output, but for some couples with composite output is still "probably prime". ${\displaystyle n\geq 5}$ ${\displaystyle a\in \{2,3,4,\dotsc ,n-2\}}$ ${\displaystyle n}$ ${\displaystyle n,a}$ ${\displaystyle n}$

Often the choice is random , the MRT in this form belongs to the class of Monte Carlo algorithms . By repeated testing with different ones, the probability of an error can be kept as small as desired. There are deterministic variants of the MRT in which an error can be excluded by a suitable choice . ${\displaystyle a}$ ${\displaystyle a}$ ${\displaystyle a}$

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

The MRI works in a similar way to the Solovay-Strassen test , but is superior to it in all aspects. It is faster, its probability of error is lower, and all pairs , for which the Solovay-Strassen test provides the correct output, are also correctly recognized by the MRI. ${\displaystyle n}$ ${\displaystyle a}$

algorithm

Let it be an odd number to determine whether it is a prime number. First you choose a number from the set . ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle \{2,3,\dotsc ,n-2\}}$

The next step is a test that only primes and strong pseudoprimes (for the base ) pass. One computes (odd) and , so that ${\displaystyle a}$ ${\displaystyle d}$ ${\displaystyle j}$

${\displaystyle n-1=d\cdot 2^{j}}$,

and then checks to see if either

${\displaystyle a^{d}\equiv 1{\pmod {n}}}$

or

${\displaystyle a^{d\cdot 2^{r}}\equiv -1{\pmod {n}}}$ for one with ${\displaystyle r}$ ${\displaystyle 0\leq r<j}$

applies. This is always the case for a prime number . If the condition is not met, it must be composed. The condition is, however, of some pairs of numbers , with composite met, so that the test, the composite character of this does not show. Then a strong pseudoprime is called the base . ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle n}$ ${\displaystyle a}$

functionality

One looks at the result

${\displaystyle (a^{d},a^{2d},a^{4d},\ldots ,a^{2^{j-1}d},a^{2^{j}d})}$,

In which each element is the square of its predecessor. The elements are calculated modulo . ${\displaystyle n}$

If a prime number, then according to Fermat's little theorem ${\displaystyle n}$

${\displaystyle a^{2^{j}d}=a^{n-1}\equiv 1{\pmod {n}}}$

and the above sequence therefore has 1 as the last element.

For prime numbers , the predecessor of a 1 in the sequence is always congruent to 1 or to -1: ${\displaystyle n}$

${\displaystyle {\begin{aligned}x^{2}\equiv 1{\pmod {n}}&\Leftrightarrow x^{2}-1\equiv 0{\pmod {n}}\\&\Leftrightarrow n|x^{2}-1\\&\Leftrightarrow n|(x-1)(x+1)\\&\Leftrightarrow n|(x-1)\quad {\text{oder}}\quad n|(x+1)\\&\Leftrightarrow x-1\equiv 0{\pmod {n}}\quad {\text{oder}}\quad x+1\equiv 0{\pmod {n}}\\&\Leftrightarrow x\equiv 1{\pmod {n}}\quad {\text{oder}}\quad x\equiv -1{\pmod {n}}\\\end{aligned}}}$

The sequence then either consists only of ones, or it contains (which results from modulo-n calculation for a value congruent to −1), which is followed by ones. If the sequence does not have this shape, it must be composed. ${\displaystyle n-1}$ ${\displaystyle (n-1)^{2}\equiv 1}$ ${\displaystyle n}$

You check whether the sequence begins with 1 or whether it appears as the penultimate element at the latest. If so, either prime or a strong pseudoprime is the base and “probably prime” is returned. Otherwise it can not be prime and the algorithm outputs “composite”. You can abort the calculation if or without a preceding one , because after that only or can come. ${\displaystyle n-1}$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle n}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle n-1}$ ${\displaystyle 0}$ ${\displaystyle 1}$

reliability

If odd and not prime, then the set contains at most elements with which are no evidence of the composite nature of . Is , then will always be for one , and will be recognized as composed. ${\displaystyle n\geq 5}$ ${\displaystyle \{2,3,\ldots ,n-2\}}$ ${\displaystyle {\tfrac {n-3}{4}}}$ ${\displaystyle a}$ ${\displaystyle \operatorname {ggT} (a,n)=1}$ ${\displaystyle n}$ ${\displaystyle g=\operatorname {ggT} (a,n)>1}$ ${\displaystyle a^{x}\equiv kg{\pmod {n}}}$ ${\displaystyle k\in \mathbb {N} }$ ${\displaystyle n}$

Is a composite odd given and it randomly selects one out , then thus the probability that the result is "probably prime" less than . If the test is repeated several times for different independently chosen ones from this set, the probability decreases further. After steps, the probability of considering a composite number to be prime is less than , e.g. B. after four steps less than 0.4% and after ten steps less than . ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle \{2,3,\ldots ,n-2\}}$ ${\displaystyle {\tfrac {1}{4}}}$ ${\displaystyle a}$ ${\displaystyle s}$ ${\displaystyle {\tfrac {1}{4^{s}}}}$ ${\displaystyle 10^{-6}}$

This is a pessimistic estimate based on the “most problematic” values ​​for . For most compounds , the proportion of bases that give a wrong result is considerably less than , and for many it is even 0. ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle {\tfrac {1}{4}}}$

Deterministic variants

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

When the tested is composite, the pseudoprimes to coprime are contained in a proper subset of . This means that when testing all of a set that is generated, one that is a witness to the composite being. If it is assumed that the Riemann Hypothesis is true, then it follows that the group is generated by its elements less than O ((log  n ) ² ), which was already stated in Miller's algorithm . The constant in Landau notation was reduced to 2 by Eric Bach. Therefore a deterministic prime number test is obtained when all are tested. The running time of this algorithm is O ((log  n ) ⁴ ). ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle \left(\mathbb {Z} /n\mathbb {Z} \right)^{*}}$ ${\displaystyle a}$ ${\displaystyle \left(\mathbb {Z} /n\mathbb {Z} \right)^{*}}$ ${\displaystyle a}$ ${\displaystyle n}$ ${\displaystyle a\in \{2,\ldots ,\min(n-1,\lfloor 2(\ln n)^{2}\rfloor )\}}$

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

• If n <1,373,653, it is enough to test a = 2 and 3,
• if n <9,080,191, it is enough to test a = 31 and 73,
• if n <4,759,123,141, it is enough to test a = 2, 7, and 61,
• if n <2,152,302,898,747, it is enough to test a = 2, 3, 5, 7, and 11,
• if n <3,474,749,660,383, it is enough to test a = 2, 3, 5, 7, 11, and 13,
• if n <341,550,071,728,321, it is sufficient to test a = 2, 3, 5, 7, 11, 13, and 17.
• if n <3,825,123,056,546,413,051, it is sufficient to test a = 2, 3, 5, 7, 11, 13, 17, 19, and 23.
• if n <318,665,857,834,031,151,167,461, it is sufficient to test a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, and 37.

Only those n may be tested that are larger than the largest specified a .

For the last example is the bound . This shows how much is saved by using only the prime numbers up to 37. ${\displaystyle a\leq \lfloor 2\cdot (\ln n)^{2}\rfloor =5857}$

See also the Prime Pages, Miller-Rabin SPRP bases records, Zhang / Tang and also the sequence A014233 in OEIS for other similar criteria. In this way, one has very fast deterministic prime number tests for numbers in the appropriate range, without resorting to unproven assumptions have to.

implementation

This C ++ implementation can handle all numbers smaller : ${\displaystyle 2^{32}}$

#include <cstdint>
using std::uint32_t;
using std::uint64_t;
bool mrt (const uint32_t n, const uint32_t a) { // n ungerade, 1 < a < n-1
   const uint32_t m = n - 1;
   uint32_t d = m >> 1, e = 1;
   while (!(d & 1)) d >>= 1, ++e;
   uint64_t p = a, q = a;
   while (d >>= 1) { // potenziere modular: p = a^d mod n
      q *= q, q %= n; // quadriere modular: q = q^2 mod n
      if (d & 1) p *= q, p %= n; // multipliziere modular: p = (p * q) mod n
   }
   if (p == 1 || p == m) return true; // n ist wahrscheinlich prim
   while (--e) {
      p *= p, p %= n;
      if (p == m) return true;
      if (p <= 1) break;
   }
   return false; // n ist nicht prim
}

Practical relevance

Primality tests are mainly needed in cryptography . A typical example is the key generation for the RSA cryptosystem , several large prime numbers are required for this. In 2002, with the AKS prime number test , a demonstrably deterministic prime number test running in polynomial time was presented for the first time. However, its runtime is usually too long for practical applications, which is why the Miller-Rabin test is usually still used for cryptography software. Although it is theoretically possible that a composite number is used as a prime number, the probability is so low that it does not matter in practice.

literature

• Johannes Buchmann : Introduction to Cryptography. 2nd Edition. Springer, 2001, pp. 108-111
• Karpfinger, Kiechle: Cryptology, Algebraic Methods and Algorithms. Vieweg + Teubner, 2010, pp. 147–152, with complete evidence

Web links

• Eric W. Weisstein : Miller-Rabin test . In: MathWorld (English).

Individual evidence

1. ^ MO Rabin: Probabilistic algorithms. In: JF Traub (ed.): Algorithms and complexity. Academic Press 1976, pp. 21-39, especially pp. 35/36, partly based on ideas from Miller
2. ^ Song Y. Yan: Number theory for computing. 2nd Edition. Springer, 2002, pp. 208-214
3. ^ Gary L. Miller: Riemann's Hypothesis and Tests for Primality. In: Journal of Computer and System Sciences 13 (1976), no. 3, pp. 300-317.
4. ↑ Eric Bach: Explicit bounds for primality testing and related problems , Mathematics of Computation 55 (1990), no. 191, pp. 355-380.
5. ^ C. Pomerance, JL Selfridge, SS Wagstaff, Jr .: The pseudoprimes to 25 · 10 ⁹ . In: Math. Comp. , 35 (1980) no. 151, pp. 1003-1026.
6. ^ Gerhard Jaeschke: On strong pseudoprimes to several bases , Math. Comp. 61 (1993), no. 204, pp. 915-926.
7. ^ Prime Pages of the University of Tennessee at Martin
8. ↑ Miller-Rabin SPRP bases records
9. ^ Zhenxiang Zhang, Min Tang: Finding strong pseudoprimes to several bases. II. In: Math. Comp. 72 (2003), pp. 2085-2097
10. ↑ The result A014233 in OEIS