The Miller-Rabin primality test, sometimes called the Rabin-Miller primality test, is a probabilistic algorithm that determines whether a given number is likely to be prime, in the same family as the Fermat primality test and the Solovay-Strassen primality test. It is of historical importance in the search for a polynomial-time deterministic primality test, and its probabilistic form remains one of the simplest and fastest primality tests in practical use. Gary L. Miller discovered the test in 1976 in a deterministic form whose correctness depends on the unproven extended Riemann hypothesis; Michael O. Rabin modified it in 1980 into an unconditional probabilistic algorithm. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/
Facts
Credited ToGary L. Miller, 1976 (deterministic form); Michael O. Rabin, 1980 (unconditional probabilistic form). 2 Classification
Design Technique Time Complexity
Time Complexity (category)Polynomial Time -- O(n^k) 1 Sources
1. Miller-Rabin Primality Test (Wikipedia)
Wikipedia infobox: time complexity polynomial
polynomial
Wikipedia: design technique randomized
randomized
View the Source2. Wikipedia: Miller-Rabin Primality Test
Wikimedia FoundationLead section
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.
entity record, description (design-technique)
The Miller-Rabin primality test, sometimes called the Rabin-Miller primality test, is a probabilistic algorithm that determines whether a given number is likely to be prime, in the same family as the Fermat primality test and the Solovay-Strassen primality test.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.