7612068647760892587567279171698469451260170146501
This factor of 49 digits from 6^250+1 was discovered on November 12, 1998 by
an automatic night job run by Michel Quercia at Lyce'e Carnot, Dijon, France.
It is the 2nd largest factor ever found by the Elliptic Curve Method (ECM)
according to the "Table of Champions" from Richard Brent [1]. This factor
completes the factorization of 6^250+1; it was known before that:
6^250+1 = 37*241*6781*343801*22243201*1748016735462726601*
1834744914758653996868853565501*c126
where c126 = 232634640586085418578351742352730448093806432162576294852640\
460489209403332406603624910153992848003268022291684080103880052501 is a
composite number of 126 digits. Michel Quercia proved it factors into
7612068647760892587567279171698469451260170146501
* 30561290412759930965030320641487022533311517309681018193831157091120980906001
where both factors are prime (primality was checked using the command
numlib::proveprime from MuPAD [2]).
The lucky curve was of the form
b*y^2*z = x^3 + A*x^2*z + x*z^2
with A=1015706534461019497980534634966901348381989468215, and has group order
2^4*3*5*101*149*179^2*223*619*2593*2969*471697*1252819*2773699*37762327.
Michel Quercia used the GMP-ECM program with first limit B1=3000000.
GMP-ECM [3] is a free implementation of ECM by Paul Zimmermann, Inria
Lorraine, France, which is based on the free GMP multiprecision library
developed by Torbjo"rn Granlund, Stockholm, Sweden.
The machine used was a Pentium 200 MMX from the Lyce'e Carnot in Dijon, France,
where Michel Quercia was teacher up to last July. On such a machine, one curve
with first limit B1=3000000 took about half an hour. Since January 1998, the
idle cycles from several computers from Lyce'e Carnot are used to help the
Cunningham project to find new factors using ECM. There are 13 PC-486-DX33,
9 Pentium-75, 17 Pentium-100, 15 Pentium-150 and 10 Pentium-200-MMX, all
running Linux and connected by a local network. Those machines can compute
about 900 curves with B1=3000000 each night, on number of about 125 digits.
An auxiliary machine keeps the information about the work remaining to be done,
switching from one number to another one by a circular permutation using NFS
in a clever way to avoid conflicts. All those machines stop their "night" work
at 8 a.m. each school day, to be used by students. An additional machine
sends an automatic mail to some people from the Cunningham project whenever
a new factor is found, or a number got enough curves, and fetches by FTP a
new number to attack. This automatic scheme worked since January 1998 with
minimal human intervention and experienced only a few problems:
- in February, during the holidays, someone disconnects a file server to
clean the room. 15 machines are hanged during 24 hours, the other go on.
After reconnecting and rebooting the file server, the hung machines
continue their computation at the point where they had stopped, as if
nothing happened.
- 28 July: the machine connecting the local net to the outside breaks down,
the machines continue with the already fetched numbers until August 10th
and then wait for the Internet link to be up again.
- end of August: the NFS server for the shared memory hangs, probably due to
a electric failure. The whole network is down during the whole day.
- beginning of November: a unknown network failure produces unreliable
results during the night.
Finally, here is the lucky run:
GMP-ECM 3a, by P. Zimmermann (Inria), 16 Oct 1998, with contributions from
T. Granlund, P. Leyland, C. Curry, A. Stuebinger, G. Woltman, JC. Meyrignac.
Input number is 232634640586085418578351742352730448093806432162576294852640460489209403332406603624910153992848003268022291684080103880052501 (126 digits)
Using B1=3000000, B2=300000000, polynomial x^30, sigma=1170774930
Step 1 took 1335260ms for 39070093 muls, 3 gcdexts
Step 2 took 631100ms for 16480797 muls, 29004 gcdexts
********** Factor found in step 2: 7612068647760892587567279171698469451260170146501
Found probable prime factor of 49 digits: 7612068647760892587567279171698469451260170146501
Probable prime cofactor 30561290412759930965030320641487022533311517309681018193831157091120980906001 has 77 digits
[1] ftp://ftp.comlab.ox.ac.uk/pub/Documents/techpapers/Richard.Brent/chams.ecm
[2] http://www.mupad.de
[3] http://www.loria.fr/~zimmerma/records/ecmnet.html
[4] http://www.matematik.su.se/~tege/gmp