Nancy, April 19, 1999
Dear ecm friends,
after a pause of several months, here is the next newsletter,
requested by some of you.
a. New large ecm factorizations (45 digits or more)
On March 25, Sam Wagstaff found a p48 from 6^726+1. Nik Lygeros and Michel
Mizony found a p47 from (157^16-1)^15+1 on March 24 and a p46 from
(2^23+2)^22+1 on February 15 (don't ask me why they consider those numbers).
Michel Quercia found a p47 from 12^495+1 on January 31. I found myself a p46
from 6^227-1 on March 23 and a p45 from 2^1330+1 on March 2. The top-10 table
from http://www.loria.fr/~zimmerma/records/ecmnet.html now contains only
factors found this year. The 1998 top-10 and the all times top-100 are also
available. Richard Brent changed the definition of ecm "champion" in 1999: it
is no longer a factor of 40 digits or more, but a factor which enters the
all-times all-programs top ten. This makes finding a champion much harder.
Only the above p48 from Wagstaff and both p47's do qualify.
b. Other large factorizations
Using SNFS, Bob Silverman and CWI factored the cofactor of 2^611+1 into
p53*p71 on March 12. With GNFS, CWI factored the cofactor of 7^241-1
(a p45 had been found last September by Andy Brown) into p52*p65.
The Cabal (a group of people using SNFS/GNFS) factored (10^211-1)/9 into
p93*p118 on April 8, a penultimate factor record. The Cabal also factored
RSA-140 using GNFS on February 2. CWI factored 2,592+1, and Conrad Curry,
after a huge effort of several months (he started last October) completed
with SNFS the factorization of 2^601-1.
c. The client/server Ecmnet project
The client/server Ecmnet project (http://www.interlog.com/~tcharron/ecm.html)
focuses on Cunningham numbers of the form 3^n-1 since January 1999.
Several successes so far include new factors from 3,505- c170, 3,597- c178,
3,509- c182, 3,469- c189, 3,559- c196, 3,527- c198, and 3,449-1 c207.
d. New version of gmp-ecm
A new version gmp-ecm 4 is available in the Ecmnet ftp directory
(source file and binaries for i686-linux, alpha-osf IRIX64 so far,
please tell me if you want other binaries).
The main change is that now step 2 uses fast polynomial multipoint
evaluation, like Peter Montgomery's ecmfft. One difference with
ecmfft is that gmp-ecm uses Karatsuba's multiplication instead of
FFT, thus step 2 costs O(B2^0.8) instead of O(B2^(1/2+epsilon)).
Another difference is that gmp-ecm uses the standard continuation,
thus it catches any prime factor up to B2 in the group order of the
elliptic curve. Here are some figures for a c120 on my PII-366 laptop
with the option -e 1 (i.e. without Brent-Suyama's improvement):
B2 step 2 time/mem suggested B1 expected curves for pxx
2.3e8 98s/ 4M 1.5e6 1100 for p35
9.6e8 5min/ 9M 4.5e6 2900 for p40
3.9e9 0h15/ 18M 15e6 6300 for p45
1.5e10 0h44/ 37M 5e7 13000 for p50
6.5e10 2h11/ 77M 15e7 25000 for p55
2.6e11 6h32/155M 45e7 50000 for p60
I recommend using version 4 only for large limits (say up from B1=10^6),
since for lower limits it is not faster nor more efficient than version 3,
and moreover it uses more memory.
Best wishes to all of you,
Paul