October 16, 1998, Nancy (France)
Dear all,
here is the table of contents of this newsletter:
1 New champions 2 Bug in GMP-ECM 3
3 Client/server utility for GMP-ECM 4 Future plans
1 New champions. Here are the new champions found since last newsletter. All
were found by GMP-ECM except the p42 from M631 which was found by mprime.
Please notice the p47 found by Aiichi Yamasaki which is the new GMP-ECM
record and 5th largest ecm factor ever found.
1385065575802663792998908771342482400851 divides A(1134,2234) P. Zimmermann
10943652034918306516518686327929621233253 divides 11^191+1 A. Brown
29811355463297742645615812791522446524687 divides 10^197+1 T. Granlund
35366018116234018504510667296204169756497 divides C(302,151)+1 A. Brown
91840062839796730661356275758867718289547 divides SymSm(39) M. Fleuren
474640860193534882628078580680807822523991 divides 2^631-1 C. Curry
10942831530607818867620259261707462111364523 divides C(334,167)+1 A. Brown
28435499313099721230022375458539937885696690833 divides 874^38+1 A. Yamasaki
Among the 14 regular Cunningham factors found in September, 10 were found by
Ecmnet. You've done good job! I also want to say that Witold Grabysz from
Poland, one of the first contributors.
2 Bug in GMP-ECM 3. There was a bug in version 3, which affects input numbers
that are near from an exact power of 2^32 or 2^64. It represents only about
2.5% of the Cunningham composites, but it's still annoying. To check that this
bug is fixed in your binary, do the following:
% echo 212252637915375215854013140804296246361 | ecm 3000000 781683988
Using B1=3000000, B2=300000000, polynomial x^30, sigma=781683988
Step 1 took 56154ms for 39070093 muls, 3 gcdexts
Step 2 took 32438ms for 16480797 muls, 29004 gcdexts
********** Factor found in step 2: 212252637915375215854013140804296246361
3 Client/server utility for GMP-ECM. Tim Charron designed a client/server
program to automatically distribute and get ecm tasks. It is available on
http://www.interlog.com/~tcharron/ecm.html. You can use it either locally
to factor your preferred numbers, or through the net. Paul Leyland set up
a master server to factor some most wanted numbers. Currently it contains
15 numbers (Cunningham, Cullen, Woodall, Smarandache), and a few people
are already helping. If you want to join us, the address of this server
is given on Tim's page. Just when I was writing this newsletter, a first
Cunningham factor was found this way, a p38 completing the factorization
of 12,555M c149. If for any reason you can't use that utility, and want
to contribute to Ecmnet, I've put together with the GMP-ECM binaries a
file c120-355.in.gz which contains about 1600 Cunningham composites.
Simply do "ecm B1 < c120-355.in > log&" where B1 is 1000000 for example.
4 Future plans. Torbjorn Granlund is currently implementing a "vertical
multiply algorithm", which uses floating-point registers to perform
integer convolution. An unoptimized implementation is running, and is
already 2 times faster than the previous mpn_mul code on some machines.
For GMP-ECM itself, my next plan is to implement the FFT continuation.
It will be version 4. I hope to have a first release next month. I plan
to implement algorithm POLYEVAL from Peter Montgomery's dissertation,
and use fast multipoint polynomial evaluation to speed up the standard
continuation. The first version will use in fact Karatsuba O(n^1.59)
multiplication algorithm instead of the O(n log n) FFT.
Ok, I've been long enough, see you next month!
Paul