best way to do "fermat" primalty checks

[Jim Fougeron]

A special purpose powm can only be done faster in a few circumstances 
(I will speak ONLY of working with huge numbers, i.e. 10's to 100's of 
thousands of bits in size).   The speed ups can be achieved through:

1. FFT utilization.   The fastest way to do this, is to put all variables into FFT 
space, and build primatives which work in FFT space (square, mult, add
reduction), so you never leave FFT until the final answer is given.  I believe
(I could VERY rightly be wrong), that GMP is not written this way, and 
does conversions into and out of FFT for each squaring/mult.  That 
is why GMP does not scale well when moving to HUGE numbers.

2. Reduce the reduction.   If a special purpose modular reduction 
can be acived, you can up to gain 3x speed improvement over
"standard" reduction methods.  

2a. This reduction of the reduction can
be taken to the extreme, and fully elminated.  That is done using 
a DWT FFT convolution.  However, this can ONLY be done effieciently 
for a VERY small range of expressions.   The prime example (pun intended)
is reduction of numbers of the form of 2^n-1 or 2^n+1.  This is the form
of number which Prime95 (GIMPS) uses.   This has the double effect of
total elimination of reduction, AND multiplication (squaring) of N bit 
number by N bit number INTO a single N bit result (normal mult/square
requires 2N result).  Thus, instead of a 3x improvement in speed, one
gets close to 6x improvement.  Some other "expression" forms can
be "squeezed" into a DWT.  These are b^n+-c and k*b^n+-c (note that
2^n-1 and 2^n+1 are simply k=1 and c=1).  However, as k and c "grow"
there is additional housekeeping tasks needed, AND additional bits of
precision needed in the FFT, and as k and or c grows, it soon becomes
less efficent to use the DWT vs using a specialized rediction (as listed
in point #2).

As for GMP, other than looking at item #1, I am not sure that a whole lot
can be done to get this type of "general purpose" math lib to perform
powm much faster for huge numbers than it does today.
 
Jim.
 
Date: 13 Nov 2005 20:28:23 +0100
From: Torbjorn Granlund <tege at swox.com>
Subject: Re: best way to do "fermat" primalty checks
To: Juergen Bullinger <juergen.bullinger at gmx.net>
Cc: gmp-discuss at swox.com
Message-ID: <86psp4bb54.fsf at king.swox.se>
Content-Type: text/plain; charset=iso-8859-1

Juergen Bullinger <juergen.bullinger at gmx.net> writes:

I am not familiar with the miller rabin test, but from what I read about
it, I think it would not be faster than the fermat check, because it
repeats something like a fermat check several times. Am I right?

Basically.

Is there anybody who can tell how much a special powm-function with a
fixed base of two would be faster than the normal powm-function?
Do you expect any difference at all?

I don't think the fact that the base is 2 could allow for any
shortcuts. However, all small bases could allow for somewhat
faster arithmetic.

If somebody would want to try to write a special mpz_powm for
that case (perhaps mpz_ui_powm) that would be a welcome
contribution to the GMP project.

--
Torbj?rn


Tray Helper - try to find something more useful... (http://www.trayhelper.com)