FW: Fermat's primality test vs. Miller-Rabin

[Charlie Kaufman]

(resending after bounce)

-----Original Message-----
From: Charlie Kaufman 
Sent: Tuesday, November 08, 2005 3:11 PM
To: 'Travis H.'; 'cryptography at 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: owner-cryptography at metzdowd.com [mailto:owner-cryptography at metzdowd.com] On Behalf Of Travis H.
Sent: Tuesday, November 08, 2005 3:05 AM
To: cryptography at 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 majordomo at metzdowd.com

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