(resending after bounce) -----Original Message----- From: Charlie Kaufman Sent: Tuesday, November 08, 2005 3:11 PM To: 'Travis H.'; 'cryptography@metzdowd.com' Subject: RE: Fermat's primality test vs. Miller-Rabin

>Is that the distinction that makes >Miller-Rabin a stronger primality test? Yes. The Miller-Rabin test will fail to detect that a Carmichael number is composite 25% of the time. Thus, repeating the Miller-Rabin test many times gives ever greater confidence. Fermat's test will fail to detect that a Carmichael number is composite 100% of the time, so repeating it doesn't help (in the fringe case of a Carmichael number). In practice, the probability of randomly choosing a Carmichael number of size >250 bits is vanishingly small. The probability of a single run of Miller-Rabin or Fermat not detecting that a randomly chosen number is composite is almost vanishingly small. I've heard but not confirmed a figure of one failure in 20 million. I've never heard an estimate of the probability that two runs would fail to detect the composite. It couldn't be better than one failure is 20 million squared or worse than one in 80 million. --Charlie Kaufman -----Original Message----- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] On Behalf Of Travis H. Sent: Tuesday, November 08, 2005 3:05 AM To: cryptography@metzdowd.com Subject: Fermat's primality test vs. Miller-Rabin 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 [EMAIL PROTECTED] --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]