Fermat's primality test vs. Miller-Rabin

[Anton Stiglic]

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