From the proof of Miller-Rabin, if a number passes the Fermat primality test, it
ID: 654420 • Letter: F
Question
From the proof of Miller-Rabin, if a number passes the Fermat primality test, it must also pass the Miller-Rabin test with the same base a (a variable in the proof). And the computation complexity is the same.
The following is from the Fermat primality test:
While Carmichael numbers are substantially rarer than prime numbers,1 there are enough of them that Fermat's primality test is often not used in the above form. Instead, other more powerful extensions of the Fermat test, such as Baillie-PSW, Miller-Rabin, and Solovay-Strassen are more commonly used.
What is the benefit of Miller-Rabin and why it is said to be more powerful than the Fermat primality test?
Explanation / Answer
The Rabin-Miller algorithm also tests, given a number n, whether Zn has a nontrivial root of Unity.
Carmichael numbers pass the Fermat test (for every basis a), but for every Carmichael number n, there exist many numbers a such that the test for unity roots fails on a (that is, the sequence a,2a,...,2ra eventually displays a nontrivial root of unity).
Thus, we have the following:
For Fermat's test, if a composite number n is not Carmichael, then the probability that the test will detect compositeness is at least 1/2. However, the test will fail all Carmichael numbers.
For the Rabin-Miller test, every composite number will be detected with probability at least 1/2. This means that the correctness probability is independent of the input (there are no "hard" inputs). This is what makes this algorithm stronger.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.