Fermat's primality test vs. Miller-Rabin

[Joseph Ashwood]

----- Original Message ----- 
From: "Charlie Kaufman" <charliek at 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 at metzdowd.com