[18934] in cryptography@c2.net mail archive
Re: Fermat's primality test vs. Miller-Rabin
daemon@ATHENA.MIT.EDU (Travis H.)
Mon Nov 14 09:33:45 2005
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Sun, 13 Nov 2005 23:15:13 -0600
From: "Travis H." <solinym@gmail.com>
To: Jeremiah Rogers <jeremiahr@vt.edu>
Cc: Alexander Klimov <alserkli@inbox.ru>, cryptography@metzdowd.com
In-Reply-To: <d8ef2d20511091009i14d787dq9bbc3f9155201dcc@mail.gmail.com>
> > Although the Carmichael numbers fool the Fermat test
> > (that is, $a^{n-1} =3D 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@metzdowd.com
