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.

StackExchange Computer Science Q#21462, answer score: 7