----- Original Message ----- From: "Charlie Kaufman" <[EMAIL PROTECTED]>
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 [EMAIL PROTECTED]

Reply via email to