(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]
