* Charlie Kaufman: > The probability of a single run of Miller-Rabin or Fermat not > detecting that a randomly chosen number is composite is almost > vanishingly small.
How do you chose a random integer, that this, based on which probability distribution? 8-) Anyway, one can show that for some fixed number, the probability that one run of the Miller-Rabin algorithm fails (i.e. reports "potentially prime" for a composite) does not exceed 1/4. Knuth gives a proof in an exercise in Volume 2 of The Art of Computer Programming, including an example that the 1/4 bound is pretty good. However, this answers a slightly different question. --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
