Fermat's primality test vs. Miller-Rabin

Jeremiah Rogers jeremiahr at vt.edu
Tue Nov 8 13:10:13 EST 2005


> It appears that Fermat's test can be fooled by Carmichael numbers,
> whereas Miller-Rabin is immune, but I'm not sure why.

Where does it say Miller-Rabin is immune to Carmichael numbers? It
seems confusingly worded and says that Fermat's Test is not immune to
Carmichaels, but this does not imply M-R is immune. Additionally, the
book says "We limit the probability of a false result [with M-R] to
2^(-128) to achieve our required security level."

> It appears that
> M-R tests that just before the squaring of a that produces a residue
> of 1, is the residue n-1.  Apparently that's not true for most bases
> of Carmichael numbers.  Is that the distinction that makes
> Miller-Rabin a stronger primality test?

To me it looks like M-R just eliminates some needless computation that
a naive application of the Fermat test would require. Computing "a^n -
a (mod n)" is harder than computing smaller powers of "a" and checking
each of those. This is why s the largest s such that 2 does not divide
s is found. If one power "q" is such that "a^(sq) - a != 0 (mod n)"
then continued squaring isn't going to generate a power of "a" that is
congruent to 1.

The "n" vs "n-1" distinction appears only when discussing if "x^2 - 1
= 0 (mod n)". This is why M-R fails for "n=2".

--
Jeremiah Rogers

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com



More information about the cryptography mailing list