[18877] in cryptography@c2.net mail archive
Re: Fermat's primality test vs. Miller-Rabin
daemon@ATHENA.MIT.EDU (Alexander Klimov)
Wed Nov 9 09:46:49 2005
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Wed, 9 Nov 2005 11:06:08 +0200 (IST)
From: Alexander Klimov <alserkli@inbox.ru>
To: cryptography@metzdowd.com
In-Reply-To: <d8ef2d20511081010n4744a2e6g455d45bbcc3228d1@mail.gmail.com>
On Tue, 8 Nov 2005, Jeremiah Rogers wrote:
> > It appears that Fermat's test can be fooled by Carmichael numbers,
> > whereas Miller-Rabin is immune, but I'm not sure why.
>
> Where does it say Miller-Rabin is immune to Carmichael numbers?
> [...]
> To me it looks like M-R just eliminates some needless computation that
> a naive application of the Fermat test would require.
I guess the small increase in efficiency would not be worth additional
program code. 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.
--
Regards,
ASK
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
