How does the Miller-Rabin primality test work?

The Miller-Rabin primality test is a fast probabilistic algorithm used to determine if a number is likely to be prime. Unlike tests that directly prove a number is prime, the Miller-Rabin test proves that a number is composite, making it a compositeness test in practice. It was originally developed by Gary L. Miller as a deterministic test relying on the extended Riemann hypothesis, and later modified by Michael O. Rabin into an unconditional probabilistic algorithm.

What we know

• The Miller-Rabin primality test is a probabilistic algorithm that determines whether a given number is likely to be prime. [2]
• Some primality tests, such as the Miller-Rabin test, prove that a number is composite rather than proving it is prime. [3]
• Gary L. Miller discovered the test in 1976 as a deterministic version whose correctness relied on the unproven extended Riemann hypothesis. [2]
• Michael O. Rabin modified Miller's version in 1980 to create an unconditional probabilistic algorithm. [2]

Where to go next

• the bigger pictureWhat was Fermat's little theorem?
• compared withHow does the Solovay-Strassen primality test work?
• whoWho were Gary Miller and Michael Rabin?
• what followedHow are primality tests used in cryptography?
• how it workedWhat is the extended Riemann hypothesis?
• an unexpected connectionHow does testing for prime numbers support the RSA cryptosystem?Probabilistic primality tests like Miller-Rabin and Solovay-Strassen hold great historical importance because they established the practical feasibility of modern public-key cryptography like RSA.

Sources

• [1]Miller–Rabin primality test (Wikidata Q980224) · CC0 1.0
• [2]Miller–Rabin primality test · CC BY-SA 4.0
• [3]Primality test · CC BY-SA 4.0
• [4]Fermat's little theorem · CC BY-SA 4.0
• [5]Solovay–Strassen primality test · CC BY-SA 4.0