Why Miller–Rabin instead of Fermat primality test?

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?

The Rabin-Miller algorithm also tests, given a number $n$, whether $Z_n$ 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,...,2^ra$ 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.

• Do you means Carmichael number n can success on Fermat's test but failed on Rabin-Miller using the same base a? – ZijingWu Feb 9 '14 at 13:15
• Carmichael numbers pass Fermat's test for every $a$, but for some $a$'s it will fail the Rabin-Miller test (specifically, the root of Unity test). – Shaull Feb 9 '14 at 15:38
• But Carmichael will not pass Fermat's test for every $a$, correct? For example the first Carmichael number 561=3*11*17 will not pass Fermat's test for $a$ = 3 or 11 or 17. – ZijingWu Feb 10 '14 at 3:52
• When we say "pass" we mean that they will not be detected as composite numbers. Thus, Carmichael numbers will pass the test for every $a$. I think we mean the same thing. In this example, 561 will pass Fermat's test for every number $a$. – Shaull Feb 10 '14 at 4:13
• The point of the "more complex" tests is that the fraction of bases which lie (say the number is perhaps prime, when it isn't) has a guaranteed limit less than 1. I.e., in Miller-Rabin it can be shown that at most 1/4 lie (IIRC, and the bound is quite pessimistic). – vonbrand Feb 10 '14 at 4:30

I believe your statement is the opposite of what happens. Passing the Miller-Rabin test for a given base means it will pass the Fermat test for the same base. In contrast, there are many composites that will pass the Fermat test for a given base but will fail the Miller-Rabin test for the same base.

See, for example, the paper by Pomerance / Selfridge / Wagstaff in the Wikipedia Miller-Rabin page:

https://math.dartmouth.edu/~carlp/PDF/paper25.pdf

where we see a diagram on page 2 showing the Euler pseudoprimes being a subset of the Fermat pseudoprimes, and the strong pseudoprimes being a subset of those. The Solovay-Strassen test is therefore more discerning than the Fermat test, and the Miller-Rabin test more than either. They both avoid the critical problem of Carmichael numbers. They have essentially the same performance, so we prefer to use the Miller-Rabin test.

It should be obvious that Miller-Rabin is better than Fermat.

With the Fermat test, we check whether $a^{p-1}$ = 1 (modulo p).

With the Miller-Rabin test, to calculate $a^{p-1}$ we find k and odd s such that $p-1 = s·2^k$. Then we calculate $a^s$ modulo p, and calculate k times the square modulo p. That's a pretty obvious way to calculate $a^{p-1}$.

Again, if the result is not 1 (modulo p) then p is composite. But if the result is 1 modulo p, then we check whether we got that 1 by squaring an intermediate result that wasn't +1 or -1, and in that case x is also proven composite.

So we do exactly the same amount of work, but there are more ways to prove that x is composite.