RabinMiller

RabinMiller, commonly referred to as the Miller–Rabin primality test, is a probabilistic algorithm used to determine whether a given integer n > 2 is prime. It improves on the basic Fermat primality test by using a strong probable prime test, which reduces the chance of false positives and makes the method practical for large numbers, such as those used in cryptography.

The test works by expressing n−1 as d · 2^s with d odd. For a chosen base a with 1 < a < n−1, one computes x = a^d mod n. If x is 1 or n−1, n passes the test for that base. Otherwise, x is repeatedly squared modulo n up to s−1 times; if any result equals n−1, n passes for that base. If none reach n−1, n is declared composite with a as a witness. Repeating the test with different bases reduces the probability that a composite number is misclassified as prime; the error probability decreases roughly by a factor of 4 with each additional independent base tested.

There are both probabilistic and deterministic variants. In the probabilistic form, a small number of random bases yields an arbitrarily small error probability. For certain ranges of n, fixed sets of bases suffice to determine primality deterministically (for example, specific bases are known to be sufficient for 32-bit or 64-bit integers).

Historically, the method arose from work by Gary L. Miller in 1976 and was independently developed and analyzed by Michael O. Rabin in 1980. The combined approach is widely used in algorithms and cryptographic applications due to its balance of speed and accuracy.