Hello, everyone!
I sent a letter to this list about a month ago indicating that Fermat number
factoring by the Elliptic Curve Method could be done more efficiently by running
curves on numbers of the form 2^(2^n) - 1 ("M-numbers") instead of running on the
Fermat numbers themselves of the form 2^(2^n) + 1 ("P-numbers"). I was finding
increases in efficiency of 3% to 15% on Athlon and Pentium III computers, mainly
because of a wider choice of FFT sizes available to Prime95 on M-numbers than on
P-numbers. George Woltman has pointed out that the increase in efficiency on Pentium
IV computers is even more dramatic, largely because the FFT code for M-numbers
incorporates use of the Pentium-IV specific SSE2 instructions, whereas the code for
P-numbers does not use this feature. As an example, I ran curves to B1=44,000,000 on
several exponents on a 1900 MHz Pentium IV and came up with the following timings:
P4096 (Fermat-12) : 3 hours, 39 minutes
P8192 (Fermat-13): 6 hours, 58 minutes
P16384 (Fermat-14): 16 hours, 51 minutes
total time for these three curves: 27 hours, 28 minutes
Then I ran a single curve on M32768 = 2^32768 - 1. This number is the product of all
the Fermat numbers from F0 to F14, and I included all known factors < 60 digits of
these Fermat numbers in the lowm.txt file. (Of course F0 through F11 are already
completely factored.) The result:
M32768: 10 hours, 16 minutes
Quite a dramatic increase in speed! George has now added the factors of these
M-numbers to the lowm.txt file, and has included a note about their use on:
http://www.mersenne.org/ecmf.htm
The combination of a fast Pentium IV with this SSE2 code makes this 1900 MHz Pentium
approximately 10 times as fast as the 400 MHz Pentium II's I was using a
year-and-a-half ago!
Good luck, anyone who wants to try this.
Phil Moore
_________________________________________________________________________
Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm
Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
