[18906] in cryptography@c2.net mail archive
FW: Fermat's primality test vs. Miller-Rabin
daemon@ATHENA.MIT.EDU (Charlie Kaufman)
Thu Nov 10 18:02:32 2005
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
From: Charlie Kaufman <charliek@exchange.microsoft.com>
To: "cryptography@metzdowd.com" <cryptography@metzdowd.com>
Date: Thu, 10 Nov 2005 14:45:49 -0800
(resending after bounce)
-----Original Message-----
From: Charlie Kaufman=20
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 Ca=
rmichael 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 si=
ze >250 bits is vanishingly small. The probability of a single run of Mille=
r-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 f=
ailure 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@metzdowd.com [mailto:owner-cryptography@metzdowd.c=
om] 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 majordomo@metzdowd.com
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
