Fermat's primality test vs. Miller-Rabin

[Travis H.]

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