> 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. Yes I guess the difference is that with MR you are trying to find a number that is *likely* a prime, whereas with Fermat you are testing primality. But MR will still fail when given a Carmichael number, since elsewhere MR is defined as iterated application of the Fermat test [1]. [1] http://www.nist.gov/dads/HTML/millerRabin.html -- Jeremiah Rogers --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]