May 15, 1998, Nancy (France)
Hello everybody,
this is the 4th ecmnet newsletter. Since last month, we welcome new
participants: Allan MacLeod, Ernst Mayer, Paul Nicholson, Andy Brown, Joe
Mikhail, Linus Nordberg, and some students of Nik Lygeros (Benoit Segain,
Cyril Aschenbrenner, Vincent Langlois, Matthieu Richard, Nicolas Serre).
Statistics. We now begin to have enough figures to make statistics about the
ecmnet project. On May 15, we have tested 85 cofactors from the Cunningham
list up to 35 digits (1800 curves with B1=1e6). From these 85 numbers, 16 new
factors were found, from 31 to 42 digits, and 6 numbers were factored
afterwards by NFS, the smallest miss being a p38. 39 numbers were tested up to
40 digits (4500 additional curves with B1=3e6): 10 factors found, one done
afterwards by NFS, smallest miss p46. Only one number was tested up to 45
digits. All that is summarized by the following table:
t35: 85 (16 factored, 6 done by someone else, smallest miss p38)
t40: 39 (10 factored, 1 done by someone else, smallest miss p46)
t45: 1 (0 factored, 0 done by someone else)
This represents a total ecm effort of about 8e11, i.e. about the total ecm
effort required to find a factor of 50 digits (in a number which contains one).
As the probability of a c150 containing a p50 factor is about 1/5, we are
about 1/5 of the expected effort to reach ecmnet goal, i.e. finding a p50.
However, this would require that we increase the values of B1 used, as with
B1=1e6 we would need about 7500 numbers to be tested up to 35 digits, with
B1=3e6 we would need about 500 numbers to be tested up to 40 digits, and
with B1=11e6 we would need about 45 numbers to be tested up to 45 digits.
Now the factors of 30 digits or more found since newsletter 3:
585857051339641816776086481697 divides F(1367) Ralf Stephan
1448595612076564044790098185437 divides Sm(58) Bruce Dodson
35065183927133465514193983196961 divides 10^403+1 Torbjorn Granlund
67415094145569534144512937880453 divides RSm(74) Paul Zimmermann
113910681722635191781067775764311 divides 2^839-1 Conrad Curry
626564962613678012662146877852049 divides 2^659-1 Conrad Curry
669995415570582921859463287135169 divides 10^328+1 Torbjorn Granlund
1459879476771247347961031445001033 divides E(58) Allan MacLeod
21023711323746974956423747989180911 divides 2^797-1 Conrad Curry
1249304905334053222308181756477664071 divides 11^255-1 Michel Quercia
557639293920224377596990976991388831169 divides 5^248+1 Paul Zimmermann
198607499132490748242152175454768755769289 divides 10^334+1 Torbjorn Granlund
Cunningham numbers. From the 9 factors found in April in the regular
Cunningham list, 5 were found by ECMNET. In extension X5, 4 out of 5
were found by ECMNET, and 2 out of 6 in extension X6. Good work!
Torbjorn Granlund found his usual set of factors of 10^n+1 and 10^n-1:
a p29 of 10,289+, a p28 of 10,449+, a p32 of 10,403+, a p33 of 10,328+.
But he is the champion of the month for the p42 from 10,334+ he found on May 7.
Michel Quercia found a p37 of 11^255-1. Linus Nordberg found a p28 of 10,417+.
Bruce Dodson will run the 2^n+1 numbers in the 1000-1200 range. Hopefully
he will be as lucky as Conrad for the 2^n-1 numbers!
Mersenne numbers. Peter Montgomery factored M(589) on April 26, finding a
p46 with his ecmfft program. Conrad Curry factored M(659) and M(839), both
factors could have been found by P-1 too. Therefore it was decided to
perform a new P-1 test on Mersenne numbers, coordinated by Will Edgington.
Conrad tested all Mersenne numbers in the 600-900 range up to 35 digits,
and also found a p35 of M(797). Eric Prestemon found the usual set of
factors: a p26 of M(1783), a p28 of M(1913), a p24 of M(1447), a p20 and a
p26 of M(1609), a p25 of M(1721), a p29 of M(1291). Rob Hooft found several
factors up to 21 digits of M(5021) to M(5387). Andy Brown rediscovered the
p47 factor of 2^391-1 (c102) using B1=11e6 and sigma=157022127.
Cullen and Woodall numbers. Paul Leyland found the usual set of factors: a p28
of C(713), a p28 of W(683), a p27 of C(528), another p27's of C(384), C(596),
C(663), W(954), a p26 of W(765), and several factors of 25 digits or less.
Fibonacci numbers. Ralf Stephan found a p25 and a p28 of F(1363),
a p29 of F(1367), a p30 of F(1367).
Smarandache numbers. Bruce Dodson found a p25 of Sm(56), a p31 of Sm(58),
a p27 of Sm(72), a p28 of RSm(75), a p27 of RSm(77). Paul Zimmermann found
a p32 of RSm(74).
Other numbers. Allan MacLeod found a p26 of T99, the 99th tangent number,
a p34 from E58, the 58th Euler number, and several other factors of tangent,
Euler and Jones numbers (see the top 100 list).
Speed improvements. My colleague Fabrice Rouillier made a new binary ecmw95.exe
(available on the same ftp site than the Unix binaries) which is about 27%
faster than Conrad Curry's MSDOS binary. But then Conrad made a new binary
(already available from the ecmnet page) which is even 5% faster on a P120.
A new version 2f of GMP-ECM was designed, which is about 20% faster for
numbers in the 120 digits range. Apart from this, the IRIX binary (32 bit) was
improved by a factor of about 3.
Top 100 list. Thanks to Torbjorn Granlund, the rank in the top 100 list is
now automatically computed by a perl script at each update. The last number
in the top 100 is currently a p23. It becomes hard to enter it!
Factorization wanted. Joe Mikhail is trying hard to factor the following c105:
434983730006829506906324587924507906930579188350117308823901731724452420995051087537386538239252454821397
If you are ready to help, please contact him .
NFS and QS code available. Bob Silverman
will make his NFS and QS code available to anyone who sends him his private
email. This may help you to complete ecm factorizations.
Thank you all for your participation to ecmnet,
Paul Zimmermann
[1] The ecmnet home page: http://www.loria.fr/~zimmerma/records/ecmnet.html