Fermat's primality test vs. Miller-Rabin

[Anton Stiglic]

>> 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 majordomo at metzdowd.com