> 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 [EMAIL PROTECTED]