[18927] in cryptography@c2.net mail archive
Re: FW: Fermat's primality test vs. Miller-Rabin
daemon@ATHENA.MIT.EDU (Florian Weimer)
Sun Nov 13 12:51:26 2005
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
From: Florian Weimer <fw@deneb.enyo.de>
To: Charlie Kaufman <charliek@exchange.microsoft.com>
Cc: "cryptography@metzdowd.com" <cryptography@metzdowd.com>
Date: Sun, 13 Nov 2005 18:05:43 +0100
In-Reply-To: <F0B4EE8E56F9DD4B80419C6D82521397624CDE@df-foxhound-msg.exchange.corp.microsoft.com>
(Charlie Kaufman's message of "Thu, 10 Nov 2005 14:45:49 -0800")
* 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@metzdowd.com
