[18919] in cryptography@c2.net mail archive
Re: Fermat's primality test vs. Miller-Rabin
daemon@ATHENA.MIT.EDU (Joseph Ashwood)
Sun Nov 13 11:31:58 2005
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
From: "Joseph Ashwood" <ashwood@msn.com>
To: <cryptography@metzdowd.com>
Date: Fri, 11 Nov 2005 21:19:59 -0800
----- Original Message -----
From: "Charlie Kaufman" <charliek@exchange.microsoft.com>
Subject: FW: Fermat's primality test vs. Miller-Rabin
> In practice, the probability of randomly choosing a Carmichael number of
> size >250 bits is vanishingly small.
I would say that finding any Carmichael number without deliberately looking
for it 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.
I can confirm that that number of completely wrong. I just implemented a
small Java program to test exactly that. Each number was vetted by a single
pass of Miller-Rabin (iterations = 1). With 512-bit numbers the first 52
random guesses that pass the first test resulted in 26 numbers that failed
to pass 128 iterations. I find it rather odd that this is exactly half, and
I also notice that of those that failed they almost all seem to have failed
at least half of them.
It appears that the minimum estimate of 1/2 probability is necessary, but
that 1/4 is more likely.
Joe
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
