[18873] in cryptography@c2.net mail archive
Re: Fermat's primality test vs. Miller-Rabin
daemon@ATHENA.MIT.EDU (Jeremiah Rogers)
Tue Nov 8 14:06:08 2005
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
Date: Tue, 8 Nov 2005 13:10:13 -0500
From: Jeremiah Rogers <jeremiahr@vt.edu>
To: "Travis H." <solinym@gmail.com>
Cc: cryptography@metzdowd.com
In-Reply-To: <d4f1333a0511080305ga4268f7s5218f944e37265d@mail.gmail.com>
> 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? It
seems confusingly worded and says that Fermat's Test is not immune to
Carmichaels, but this does not imply M-R is immune. Additionally, the
book says "We limit the probability of a false result [with M-R] to
2^(-128) to achieve our required security level."
> It appears that
> M-R tests that just before the squaring of a that produces a residue
> of 1, is the residue n-1. Apparently that's not true for most bases
> of Carmichael numbers. Is that the distinction that makes
> Miller-Rabin a stronger primality test?
To me it looks like M-R just eliminates some needless computation that
a naive application of the Fermat test would require. Computing "a^n -
a (mod n)" is harder than computing smaller powers of "a" and checking
each of those. This is why s the largest s such that 2 does not divide
s is found. If one power "q" is such that "a^(sq) - a !=3D 0 (mod n)"
then continued squaring isn't going to generate a power of "a" that is
congruent to 1.
The "n" vs "n-1" distinction appears only when discussing if "x^2 - 1
=3D 0 (mod n)". This is why M-R fails for "n=3D2".
--
Jeremiah Rogers
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
