On Wed, 9 Nov 2005, Jeremiah Rogers wrote: > > 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.

For large n the ratio s to log n is small (where n-1 = d 2^s) and s is exactly the number of multiplication you may hope to avoid. > But MR will still fail when given a Carmichael number, > since elsewhere MR is defined as iterated application of the Fermat > test. It is very easy to check. 561 is a Carmicael number (the smallest one), for example, for a = 2 2^560 = 1 (561) and the same for all a's coprime to 561. Btw, 651 = 3*11*17, so don't try with a = 3 :-) Let us now go to the RM test: 560 = 35 * 2^4 (d = 35 and s = 4), so, e.g., for a = 2, 2^35 = 263 (that is a^d \ne 1) and 263^2 = 166, 166^2 = 67, 67^2 = 1 (that is a^{2^r d} \ne -1 \forall r \in [0, s-1]), so RM test declares that 561 is composite and 2 is a strong witness of this. -- Regards, ASK --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]