Henk Stokhorst writes:
I simplified the code a little bit, it says divide, whereas in the
real code fourier transformations seem to be used. But I assumed
more people would be familiar with dividing than fourier
transformatios.
The factoring code does not use fourier transformations; only the
squaring code of the Lucas-Lehmer test needs that.
But rather than having to even calculate, let alone divide anything
into, the Mersenne number itself, the factoring code (in both Prime95
and the mers package trial factorers) calculates (2^exponent) modulo
the trial factor a bit (literally) of the exponent at a time,
something like this:
acc = 2;
topbit = 2;
while (topbit <= exponent)
topbit = 2*topbit;
for (bit = topbit/2; bit > 0; bit = bit/2)
acc = (acc*acc) % trial_factor;
if (exponent & bit) /* is this bit set/on in the exponent? */
acc = 2*acc;
if (acc == (trial_factor + 1))
found_a_factor(trial_factor);
... where '%' is the C modulo (remainder) operator and '&' is the C
bit-wise and operator. The comparison to trial_factor + 1 rather than
to just 1 is because the last '2*acc' is not '(2*acc) % trial_factor'.
Will
