September 17, 1998, Nancy (France)

	Dear all,

53 digits! This is the new factorization record by the Elliptic Curve Method
(ECM). It was set by Conrad Curry on September 14, 1998, using George Woltman's
mprime program. Conrad found the following factor of 2^677-1 which has a
cofactor of 150 digits:

	p=53625112691923843508117942311516428173021903300344567

This factor could not have been found by p-1 nor p+1 since:

p-1 = 2*3*11*13*17*677*6967*690915503*1128164921145703871469544532080003
p+1 = 2*2*2*29*181*888011*483546151552771*2974030248726116125294487359

The c150 cofactor was also very difficult for SNFS (Peter Montgomery had
computed a NFS difficulty of about 203.80, which corresponds to about two
cpu years from a R10K machine). The official announce from Conrad can be
found at http://www.loria.fr/~zimmerma/records/p53. Congratulations to
Conrad and to George for his very efficient program!

This new record makes Richard Brent's prediction from 1985 true, which was
the primary goal of the Ecmnet project. I took that opportunity to trace
the history of the ECM records since 1991. The previous records were:
a p49 factor from 2^1071+1 c132 found by Paul Zimmermann on June 19, 1998;
a p48 factor from 24^121+1 c130 found by Richard P. Brent on October 9, 1997;
a p47 factor from 30^109-1 c89 found by Peter Montgomery on February 25, 1996;
a p47 factor from 5^256+1 c134 found by Peter Montgomery on November 27, 1995;
a p44 factor from p(19069) c99 found by Berger-Mueller on June 21, 1995;
a p43 factor from p(19997) c139 found by Berger-Mueller on March 20, 1993;
a p42 factor from 10^201-1 c111 found by D. Rusin on April 5, 1992;
a p40 factor from p(11279) c89 found by Lenstra-Dixon on October 28, 1991.

Apart from that p53, a lot of new factors were found last month. I will
cite only those of 40 digits or more:

mprime:
41283139633378645724930694480520226273492263 divides 2^673-1 J. Meyrignac

GMP-ECM:
1065257258169240607135936699425183122779 divides C(286,143)+1 A. Brown
1224533922806644880889416498956645819661 divides W(399) P. Leyland
544919289684132720332849364364039531371953 divides 2^2011-1 J. A. Card
1779404518834461451106638053005866162077187 divides p(16931) E. Prestemon
547283138069536869412948975377385222182769003 divides 7^241-1 A. Brown

ecmfft:
1319762353105502239973877413549107890281 divides 23^140+1 P. Montgomery
1965747791813662647853744409824247719823 divides p(17497) B. Dodson
152534412777371020101940888807247213877161 divides 38^95+1 P. Montgomery
2016492306990976282439501774196098215666169 divides 10^221+1 B. Dodson
2994000169930481672558671908900434599628639 divides p(19013) B. Dodson
56114349979147421395738682578959695611260961 divides 12^220+1 B. Dodson

So far, 53 new champions were found in 1998 (is 53 a magic number?), over
a total of 126 champions in "all times". Hence it is very possible that the
total number of champions will double in 1998.

Concerning Ecmnet, two main contributors, Nik Lygeros and Paul Nicholson, 
found their first factor, resp. a p32 from 6^375-1 and a p38 from 7^223+1.

A new release of GMP-ECM is available (source code + binaries as usual).
For version, I have completely rewritten stage 2. It is 10% faster,
uses much less memory, and it now includes Suyama's idea of raising the
values computed to some power e. Previous versions of GMP-ECM used e=1,
and you can get the same behaviour with the option -e 1:

% time ecm2i.alpha 1000000 < c120
GMP-ECM 2i, by P. Zimmermann (Inria), August 1998, with contributions from
T. Granlund, P. Leyland, C. Curry, A. Stuebinger, G. Woltman, JC. Meyrignac.
Input number is 265535466579688604805851295242389350646124229512840469920696404242681668380354424870495084413250865968329058772250534133 (120 digits)
Using B1=1000000 and sigma=1884554766
Step 1 took 80164ms for 12986907 muls, 2 gcds, 2 gcdexts
Step 2 took 39718ms for 5431072 muls, 1 gcd(s), 10003 gcdexts

% time ecm3.alpha -e 1 1000000 < c120
GMP-ECM 3, by P. Zimmermann (Inria), 17 Sep 1998, with contributions from
T. Granlund, P. Leyland, C. Curry, A. Stuebinger, G. Woltman, JC. Meyrignac.
Input number is 265535466579688604805851295242389350646124229512840469920696404242681668380354424870495084413250865968329058772250534133 (120 digits)
Using B1=1000000, B2=100000000, polynomial x^1, sigma=583524959
Step 1 took 72733ms for 12986907 muls, 3 gcdexts
Step 2 took 33190ms for 4921535 muls, 8195 gcdexts

% time ecm3.alpha 1000000 < c120
GMP-ECM 3, by P. Zimmermann (Inria), 17 Sep 1998, with contributions from
T. Granlund, P. Leyland, C. Curry, A. Stuebinger, G. Woltman, JC. Meyrignac.
Input number is 265535466579688604805851295242389350646124229512840469920696404242681668380354424870495084413250865968329058772250534133 (120 digits)
Using B1=1000000, B2=100000000, polynomial x^18, sigma=838833223
Step 1 took 72756ms for 12986907 muls, 3 gcdexts
Step 2 took 41299ms for 5771003 muls, 12687 gcdexts

Suyama's extension improves the efficiency of stage 2. With B1=1,000,000
and x^18 (default), now only about 1100 curves instead of 1800 should be 
enough to test a number up to p35; with B1=3,000,000 and x^30 (default),
about 3000 curves instead of 5080 should be enough to test up to p40.

Finally, Allan MacLeod improved ecmloop.bat so that it does not stop after
a factor is found. Tim Charron even made an ecmloop2.bat file that automa-
tically increases the first limit B1. Tim is also working on a client/server
program to automatically distribute or get Ecmnet work. And Hisanori Mishima
maintains some nice tables with (alternating or not) sums of factorials,
Euler and Bernoulli numbers, and Products of primes - Next prime; see
http://www.asahi-net.or.jp/~KC2H-MSM/mathland/matha1.

Correction: Cullen(361275) is a true prime, and not a probable-prime as 
stated in newsletter 7.

Best wishes to all of you,
Paul Zimmermann