`----- 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 ofsize >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 detectingthat 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'venever heard an estimate of the probability that two runs would fail todetect the composite. It couldn't be better than one failure is 20 millionsquared 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]