Why Miller–Rabin instead of Fermat primality test?

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.