Fermat's primality test vs. Miller-Rabin

[Alexander Klimov]

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