Fermat's primality test vs. Miller-Rabin

[Travis H.]

In "Practical Cryptography", Schneier states that the you can prove
that when n is not a prime, a certain property of a mod n holds for at
most 25% of possible values 1 < a < n.  He later states that Fermat's
test can be fooled by Carmichael numbers, and finally he basically
says that Miller-Rabin is based on Fermat's test.

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

It's amazing how many words that took to state, and I didn't even
specify the squaring process.
--
http://www.lightconsulting.com/~travis/  -><-
"We already have enough fast, insecure systems." -- Schneier & Ferguson
GPG fingerprint: 50A1 15C5 A9DE 23B9 ED98 C93E 38E9 204A 94C2 641B

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