Editing Miller–Rabin primality test (section)

{{short description|Probabilistic 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 [[probable prime|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 Miller (professor)|Gary L. Miller]] discovered the test in 1976. Miller's version of the test is [[deterministic algorithm|deterministic]], but its correctness relies on the unproven [[extended Riemann hypothesis]].<ref name="miller">{{Citation |last=Miller |first=Gary L. |year=1976 |title=Riemann's Hypothesis and Tests for Primality |author-link=Gary Miller (computer scientist) |journal=Journal of Computer and System Sciences |volume=13 |issue=3 |pages=300–317 |doi=10.1145/800116.803773 |s2cid=10690396 }}</ref> [[Michael O. Rabin]] modified it to obtain an unconditional [[randomized algorithm|probabilistic algorithm]] in 1980.<ref name="rabin">{{Citation |last=Rabin |first=Michael O. |year=1980 |title=Probabilistic algorithm for testing primality |author-link=Michael O. Rabin |journal=Journal of Number Theory |volume=12 |issue=1 |pages=128–138 |doi=10.1016/0022-314X(80)90084-0 |doi-access= }}</ref>{{efn|
The Miller–Rabin test is often incorrectly said to have been discovered by {{nobr|M. M. Artjuhov}} as soon as 1967; a reading of Artjuhov's paper<ref>{{citation
 | last = Artjuhov | first = M. M.
 | journal = Acta Arithmetica
 | mr = 0213289
 | pages = 355–364
 | title = Certain criteria for primality of numbers connected with the little Fermat theorem
 | volume = 12
 | year = 1966–1967}}</ref>
(particularly his {{nobr|Theorem E}}) shows that he actually discovered the Solovay–Strassen test.
}}