NIST

Miller-Rabin

(algorithm)

Definition: A heuristic test for prime numbers. It repeatedly checks if the number being tested, n, is pseudoprime to a randomly chosen base, a, and there are only trivial square roots of 1, modulo n. In other words, n is surely composite if an-1 ≠ 1 (mod n), where 0 < a < n. Some composites may be incorrectly judged to be prime.

Note: For k repetitions, the chance of incorrectly judging an odd integer greater than 2 to be prime is 2-k. For randomly chosen large integers, a small number of repetitions, say 3, is enough. After [CLR90, pages 838-844].

Author: PEB


Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 14 December 2005.
HTML page formatted Mon Feb 2 13:10:39 2015.

Cite this as:
Paul E. Black, "Miller-Rabin", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 14 December 2005. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/millerRabin.html