>> 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 [EMAIL PROTECTED]