[18905] in cryptography@c2.net mail archive
Re: Fermat's primality test vs. Miller-Rabin
daemon@ATHENA.MIT.EDU (Anton Stiglic)
Thu Nov 10 18:01:58 2005
X-Original-To: cryptography@metzdowd.com
X-Original-To: cryptography@metzdowd.com
From: Anton Stiglic <astiglic@okiok.com>
In-Reply-To: <d8ef2d20511091009i14d787dq9bbc3f9155201dcc@mail.gmail.com>
Date: Thu, 10 Nov 2005 13:36:51 -0500 (EST)
To: "Jeremiah Rogers" <jeremiahr@vt.edu>
Cc: "Alexander Klimov" <alserkli@inbox.ru>, cryptography@metzdowd.com
>> 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.
>
> 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].
That is not true, in several counts.
Firstly Miller-Rabin probabilistic primality test doesn't generate a
number, it verifies a number for primality.
Secondly, the Miller-Rabin probabilistic primality test is not based on
Fermat's Little theorem, or so called pseudoprime test, but rather on the
strong pseudoprime test, which derives from a theorem that says that if n
is an odd prime, n-1 = 2^s * r with r odd, then for any a such that
gcd(a,n) = 1 either a^r == 1 (mod n) or a^(r*2^j) == -1 (mod n) for some
j, 0 <= j <= s-1. See Handbook of a applied cryptography fact 4.20.
I'm affraid the reference you gave is incorrect.
--Anton
---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo@metzdowd.com
