Alexander Kruppa writes:
I saw code posted earlier today that did LL testing with the GMP
library. It used the mpz_powm_ui function for exponentiating modulo
x. For x=2**p-1 this function can be sped up considerably, since a
mod (2^p-1) = a % 2^p + a / 2^p (integer operations) and these can
be done by bit shifting/masking.
Yup; good eye. I figured this out years ago, but I think the only
place it's presently used in the mers package is in mers3p. The LL
test programs do the modulo as part of the FFT, though, so it would
actually slow them down.
I use this function below for my P-1 factorer (not released (yet?)).
It gave me a factor 3 speedup. It�s a pretty straigtforward
exponentiation algo
exp(b,e) = if (e & 1) b*exp(b**2,e >>1) else exp(b**2,e >>1)
with the modulo by bit shifting.
This is what the trial factorers, George's and the mers package's, do,
except that the modulo is by the trial factor, and thus can't be sped
up this way but allows the use of single word arithmetic, and the
exponentiation is of two. George told me about it and we put it in my
pre-GIMPS trial factorer, which also gave it a speed up of a factor of
three or so.
To Will Edington: I think I saw in the P-1 factorer of the mers
package that it used mpz_powm_ui, too, perhaps you may want to
replace it.
Yup, when I get around to it. But that program is so slow, noone is
using it so far as I'm aware. It also does not support save files.
What would be really nice is if someone that understands the FFT code
of MacLucasUNIX, mersenne1, or even fftlucas would use that knowledge
to write a P-1 and/or ECM factorer. I'd do it myself, except that I
don't understand FFTs themselves enough, let alone the mers package
programs that implement them.
Will
