Миллер-Рабин сандық жайлылық тесті

Primality test
The Miller–Rabin primality test or Rabin–Miller primality test is a probabilistic primality test: an algorithm which determines whether a given number is likely to be prime, similar to the Fermat primality test and the Solovay–Strassen primality test. It is of historical significance in the search for a polynomial time deterministic primality test. Its probabilistic variant remains widely used in practice, as one of the simplest and fastest tests known. Gary L. Miller discovered the test in 1976. Miller's version of the test is deterministic, but its correctness relies on the unproven extended Riemann hypothesis. Michael O. Rabin modified it to obtain an unconditional probabilistic algorithm in 1980.

Similarly to the Fermat and Solovay–Strassen tests, the Miller–Rabin primality test checks whether a specific property, which is known to hold for prime values, holds for the number under testing.

Thankfully, no composite number is a strong pseudoprime to all bases at the same time (contrary to the Fermat primality test for which Fermat pseudoprimes to all bases exist: the Carmichael numbers). However no simple way of finding a witness is known. A naïve solution is to try all possible bases, which yields an inefficient deterministic algorithm. The Miller test is a more efficient variant of this (see section Miller test below). Another solution is to pick a base at random. This yields a fast probabilistic test. When n is composite, most bases are witnesses, so the test will detect n as composite with a reasonably high probability (see section Accuracy below). We can quickly reduce the probability of a false positive to an arbitrarily small rate, by combining the outcome of as many independently chosen bases as necessary to achieve the said rate. This is the Miller–Rabin test. There seems to be diminishing returns in trying many bases, because if n is a pseudoprime to some base, then it seems more likely to be a pseudoprime to another base. Note that a^(d) ≡ 1 (mod n) holds trivially for a ≡ 1 (mod n), because the congruence relation is compatible with exponentiation. And 1=a^(d) = a^(2^(0)d) ≡ −1 (mod n) holds trivially for a ≡ −1 (mod n) since d is odd, for the same reason. That is why random a are usually chosen in the interval 1 < a < n − 1. For testing arbitrarily large n, choosing bases at random is essential, as we don't know the distribution of witnesses and strong liars among the numbers 2, 3, , n − 2. However, a pre selected set of a few small bases guarantees the identification of all composites up to a pre computed maximum. This maximum is generally quite large compared to the bases. This gives very fast deterministic tests for small enough n (see section Testing against small sets of bases below).

Here is a proof that, if n is a prime, then the only square roots of 1 modulo n are 1 and −1. Here is a proof that, if n is an odd prime, then it is a strong probable prime to base a.

Using repeated squaring, the running time of this algorithm is [[Big O notation, where n is the number tested for primality, and k is the number of rounds performed; thus this is an efficient, polynomial time algorithm. FFT based multiplication (Harvey Hoeven algorithm) can decrease the running time to .