>> 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].

That is not true, in several counts. Firstly Miller-Rabin probabilistic primality test doesn't generate a number, it verifies a number for primality. Secondly, the Miller-Rabin probabilistic primality test is not based on Fermat's Little theorem, or so called pseudoprime test, but rather on the strong pseudoprime test, which derives from a theorem that says that if n is an odd prime, n-1 = 2^s * r with r odd, then for any a such that gcd(a,n) = 1 either a^r == 1 (mod n) or a^(r*2^j) == -1 (mod n) for some j, 0 <= j <= s-1. See Handbook of a applied cryptography fact 4.20. I'm affraid the reference you gave is incorrect. --Anton --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]