[18903] in cryptography@c2.net mail archive
Re: Fermat's primality test vs. Miller-Rabin
daemon@ATHENA.MIT.EDU (Anton Stiglic)
Thu Nov 10 16:53:10 2005
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
From: Anton Stiglic <astiglic@okiok.com>
In-Reply-To: <d8ef2d20511091009i14d787dq9bbc3f9155201dcc@mail.gmail.com>
Date: Thu, 10 Nov 2005 13:55:36 -0500 (EST)
To: "Jeremiah Rogers" <jeremiahr@vt.edu>
Cc: "Alexander Klimov" <alserkli@inbox.ru>, cryptography@metzdowd.com
>> I guess the small increase in efficiency would not be worth additional
>> program code.
>
> That depends on the size of the numbers you're working with...
> Considering the research that goes into fast implementations of
> PowerMod I don't think the required computation is trivial.
>
>> Although the Carmichael numbers fool the Fermat test
>> (that is, $a^{n-1} = 1 (n)$) for *all* a, there are no such things for
>> the Miller-Rabin test: for any odd composite n at least 3/4 of a's
>> fail the test, that is if you made m MR tests with random a's then you
>> are mistaken with probability at most (1/4)^m.
That is true but is not the result of a direct conclusion. Let X
represent the event that n is composite, and Y_t the event that
MILLER-RABIN(n,t) declares n to be prime. Because for a composite n there
is at least 3/4 of a's that fail the test, we can conclude that Pr(Y_t |
X) <= (1/4)^t.
But the probability I think you are referring to (the one that is usually
considered the most interesting) is P(X | Y_t). It happens to be the case
that P(X | Y_t) is in fact <= (1/4)^t when using uniform random
candidates, but to come to that conclusion you need to consider the fact
that the error probability of Miller-Rabin is usually far smaller than
(1/4)^t (and apply Bayes theorem and a theorem on the distribution of
prime numbers). See Note 4.47 in the Handbook of applied cryptography, or
the following paper:
http://www.cs.mcgill.ca/~crepeau/PS/BBC+87.ps
--Anton
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
