Fermat's primality test vs. Miller-Rabin

[Alexander Klimov]

On Wed, 9 Nov 2005, Jeremiah Rogers wrote:

> > I guess the small increase in efficiency would not be worth additional
> > program code.
>
> That depends on the size of the numbers you're working with...
> Considering the research that goes into fast implementations of
> PowerMod I don't think the required computation is trivial.

For large n the ratio s to log n is small (where n-1 = d 2^s) and s is
exactly the number of multiplication you may hope to avoid.

> But MR will still fail when given a Carmichael number,
> since elsewhere MR is defined as iterated application of the Fermat
> test.

It is very easy to check.

561 is a Carmicael number (the smallest one), for example, for a = 2
2^560 = 1 (561) and the same for all a's coprime to 561.
Btw, 651 = 3*11*17, so don't try with a = 3 :-)

Let us now go to the RM test:  560 = 35 * 2^4 (d = 35 and s = 4), so,
e.g., for a = 2, 2^35 = 263 (that is a^d \ne 1) and
263^2 = 166, 166^2 = 67, 67^2 = 1 (that is a^{2^r d} \ne -1 \forall r
\in [0, s-1]), so RM test declares that 561 is composite and 2 is a
strong witness of this.

-- 
Regards,
ASK

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com