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