November 23, 1998, Nancy (France)
Dear all,
sorry for this late newsletter. I hope you didn't wait too long for it!
In case you prefer to read it directly on the Ecmnet web page [1], just
tell me and I'll remove your name from my list.
New champions. Since last newsletter from October 16, 14 new champions were
found using gmp-ecm. The most impressive is the p49 from 6^250+1 found by
Michel Quercia on November 12. It is the 2nd largest factor ever found by
ecm [3], and by far the largest one found by gmp-ecm. I'm happy that Michel
found that one since he is one of the first Ecmnet contributors. Click on
the p49 on the Ecmnet page for more details about this record factorization.
1418947407135944407724674796954045966107 divides 910^63-1 M. Ukai
2312059088305137367965589910642918744521 divides 987^38+1 A. Yamasaki
10196967075663269987674261493780609108227 divides p(21187) P. Zimmermann
11555516101313335177332236222295571524323 divides Sm(70) T. Charron/Ecmnet
13231286310635194760975216003886759010777 divides 2^1774+1 P. Zimmermann
17150218359779837381260310627673607103329 divides p(25237) P. Zimmermann
36484622801212335399694058664718840029121 divides 2^1294+1 P. Zimmermann
295666607855148525951669299929669849601357 divides 10^389-1 T. Granlund
663636889167401354279502795531186216903001 divides 2^1005-1 T. Nøkleby/Ecmnet
739762335239015186706527735192795520726707 divides Euler(84) A. MacLeod
16937690868390879532181520681947735653224689 divides p(26711) P. Zimmermann
37835716074058426890725596550304118196498159 divides Bernoulli(152) A. MacLeod
914570427675304311896510460383772935570463409 divides 2^1614+1 P. Zimmermann
7612068647760892587567279171698469451260170146501 divides 6^250+1 M. Quercia
Among those 14 new champions, the two acknowledged "Ecmnet" were found using
Tim Charron's client/server setup [4], which runs both on Windows and Unix
machines. Tim maintains a nice summary of factors found using his client/server
setup on his "factors.html" page.
Faster Linux binary. Thanks to some remarks from Jean-Charles Meyrignac who
compared the x86/Pentium/PentiumII assembler routines, Torbjo"rn Granlund
found a way to improve the multiplication in GMP by a factor of about two.
The resulting gain for gmp-ecm is about 15%. I've put a new Linux binary
ecm3b.i686.linux.gz in the ecmnet ftp directory. Here is what you should
get on a PII-400:
GMP-ECM 3b, by P. Zimmermann (Inria), 17 Nov 1998, with contributions from
T. Granlund, P. Leyland, C. Curry, A. Stuebinger, G. Woltman, JC. Meyrignac.
... and the invaluable help from P.L. Montgomery.
Input number is 265535466579688604805851295242389350646124229512840469920696404242681668380354424870495084413250865968329058772250534133 (120 digits)
Using B1=30000, B2=3000000, polynomial x^6, sigma=744211521
Step 1 took 4090ms for 384595 muls, 3 gcdexts
Step 2 took 2990ms for 225155 muls, 1856 gcdexts
There is no main change in the program this month. I'm still working on the
fast multipoint evaluation for step 2, but rather slowly. Anyway, the current
version is not so bad. Will another p50 be found before the end of 1998 ?
I would not bet the answer is "no".
Paul Zimmermann
[1] http://www.loria.fr/~zimmerma/records/ecmnet.html
[2] http://www.loria.fr/~zimmerma/records/p49b.announce
[3] ftp://ftp.comlab.ox.ac.uk/pub/Documents/techpapers/Richard.Brent/chams.ecm
[4] http://www.interlog.com/~tcharron/ecm.html