FW: Fermat's primality test vs. Miller-Rabin

[Florian Weimer]

* 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 majordomo at metzdowd.com