Fermat's primality test vs. Miller-Rabin

[Jeremiah Rogers]

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