> > Although the Carmichael numbers fool the Fermat test
> > (that is, $a^{n-1} = 1 (n)$) for *all* a,I thought it would work properly if a shares a factor with n. > 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]. I hate to jump on the bandwagon about this, but these statements fail a basic consistency test. Iterating a deterministic test will not generate a probabilistic one. And since the Fermat test fails for Carmichael numbers, I wouldn't say that it's testing primality. Both tests are probabilistic, and return answers of "composite" or "answer unclear" for a chosen basis. MR does appear to save some exponentiations, but it also appears to check that the last (temporally) non-1 square root of 1 we used was -1, which it must be if n is prime, making it a stronger test than Fermat's. Wikipedia concurs that MR is preferred over Fermat, primarily (pun intended) because of Carmichael numbers. -- http://www.lightconsulting.com/~travis/ -><- "We already have enough fast, insecure systems." -- Schneier & Ferguson GPG fingerprint: 50A1 15C5 A9DE 23B9 ED98 C93E 38E9 204A 94C2 641B --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
