===============================================================================
Large Factors Found By ECM in 1999
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
This file (champs99.txt) contains information on large factors
found by the elliptic curve factoring method (ECM). Factors are
included if
1) they were at any time the largest factor found so far by ECM
and at least 40 decimal digits ("champions"); or
2) they are one of the largest ten factors found so far (the "top ten").
New entries will be accepted if they are in the current "top ten".
At present this means they will have to be at least 48 decimal digits.
In 1999 there were nine new entries (one p54, one p52, one p50, one p49,
three p48, two p47), but the two p47 and two p48 have already dropped off the
list, leaving five new entries.
The largest factor so far, found by Nik Lygeros and Michel Mizony using
GMP-ECM, has 54 decimal digits.
The overall list is given below. Factors which at one time were the current
"champions" are marked by an asterisk.
This file is available from
ftp://ftp.comlab.ox.ac.uk/pub/Documents/techpapers/Richard.Brent/champs.txt
Please send corrections/updates to rpb@comlab.ox.ac.uk
R. P. Brent
http://www.comlab.ox.ac.uk
===============================================================================
Summary
^^^^^^^
Factor Divides Found by Date
p54 ^^^^^^ ^^^^^^^ ^^^^^^^^ ^^^^
^^^ YYYYMMDD
484061254276878368125726870789180231995964870094916937 *
(6^43-1)^42+1 Note (11) 19991226
p53
^^^
53625112691923843508117942311516428173021903300344567 *
2,677- C. Curry (8) 19980914
p52
^^^
2414704785479757305369621862192236137072000732339933
96,98+ P. Montgomery (5) 19990729
p50
^^^
28352547568921790651747638524393003422138037231571
3,1179L P. Zimmermann (13) 19991013
p49
^^^
7612068647760892587567279171698469451260170146501
6,250+ M. Quercia (9) 19981112
2359597690909288137577710805751790832324948920367
(14^82-1)^81+1 Note (10) 19991028
1078825191548640568143407841173742460493739682993 *
2,1071+ P. Zimmermann (7) 19980619
p48
^^^
901584692755427378722839770656354167189649601351
2,695- C. Curry (12) 19990607
662926550178509475639682769961460088456141816377 *
24,121+ R. P. Brent (6) 19971009
595580447139800838293908535595226727082115962317
p(20219) B. A. Dodson (4) 19981206
[end of current top ten]
[following former champions listed for historical interest]
p47
^^^
28207978317787299519881883345010831781124600233 *
30,109- P. Montgomery (5) 19960225
12025702000065183805751513732616276516181800961 *
5,256+ P. Montgomery (5) 19951127
p44
^^^
27885873044042449777540626664487051863162949 *
p(19069) Berger-Mueller (3) 19950621
p43
^^^
5688864305048653702791752405107044435136231 *
p(19997) Berger-Mueller (3) 19930320
p42
^^^
184976479633092931103313037835504355363361 *
10,201- D. Rusin (2) 19920405
p40
^^^
1232079689567662686148201863995544247703 *
p(11279) Lenstra-Dixon (1) 19911028
Notes
^^^^^
Factors divide numbers of the form a^n +- 1 (abbreviated a,n{+-LM})
or partition numbers (p(n) is the n-th partition number)
or Lucas numbers (Ln is the n-th Lucas number).
Dates are in YYYYMMDD format.
(1) Arjen Lenstra and Brandon Dixon on a MasPar (the first p40 by ECM).
(2) David Rusin using Peter Montgomery's program.
(3) Franz-Dieter Berger and Andreas M\"uller on a network of workstations.
(4) Bruce Dodson with Peter Montgomery's program.
(5) Peter Montgomery on an SGI workstation.
(6) Richard Brent on a Fujitsu VPP300.
(7) Paul Zimmermann on an SGI Power Challenge with Montgomery's program.
(8) Conrad Curry with George Woltman's mprime program using 16 Pentiums.
(9) Michel Quercia with GMP-ECM.
(10) Nik Lygeros and Michel Mizony with GMP-ECM.
(11) Nik Lygeros and Michel Mizony with GMP-ECM. If b = 6^43-1, the input
was c127 = (b^6+1)/(b^2+1)/13/733/7177.
(12) Conrad Curry with George Woltman's program on a 400MHz Pentium P-II.
(13) Paul Zimmermann on a Dec Alpha with GMP-ECM
===============================================================================
Information on Curves and Group Orders
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
If g is the order of the group used to find the factor, the following
table gives the second-largest prime factor (g2)
and the largest prime factor (g1) of g, where known.
In some cases the exact values are not known, but bounds
can be given from knowledge of the phase 1 and phase 2 limits.
This is indicated by the "<" and ">" symbols.
The values of g2 and g1 have been deduced from the information given
in the "Details" section below and have not been verified independently.
C = C(g1,g2) = 1/mu, where mu is an estimate of the probability that
a random integer close to p/12 has largest prime factor at most g1
and second-largest prime factor at most g2. Thus, C is an estimate
of the expected number of curves to find the factor with phase 1
limit g2 and phase 2 limit g1. This assumes that the curves are chosen
so that the group order is divisible by 12, which was not always the case
for the computation which found the factor. It also assumes that group
orders behave like random integers (apart from being a multiple of 12).
The larger C, the more "improbable" it is that the group order is so smooth.
If the elliptic curve is known to be of the form b*y^2 = x^3 + a*x^2 + x
with initial point (x1, y1), where x1 = u^3, u = (sigma^2 - 5)/(4*sigma),
a + 2 = (1/u - 1)^3 * (3*u + 1)/4, then the parameter sigma is given.
In this case the group order is divisible by 12.
Factor g2 g1 C sigma
^^^^^^ ^^^^ ^^^^ ^^^ ^^^^^
p54 = 4840... 8939393 13323719 4400000 599841120
p53 = 5362... 8867563 15880351 2400000 8689346476060549
p52 = 2414... 25190591 30318953051 39000
p50 = 2835... 840299 1315315249 1700000 2009193935
p49 = 7612... 2773699 37762327 720000 1170774930
p49 = 2359... 2654917 316054537 300000 1656203751
p49 = 1078... 28393447 2700196643 16000
p48 = 9015... 6747353 35174779 210000 42254462032221
p48 = 6629... 141667 150814537 29000000 876329474
p48 = 5955... 3973447 9010207411 67000
p47 = 2820... 1127603 209558929 370000
p47 = 1202... 2459497 903335969 85000
p44 = 2788... 949159 4818400261 49000
p43 = 5688... < 139894 < 14212100 > 2300000
p42 = 1849... < 2000000 < 100000000 > 20000
p40 = 1232... < 1000000 1209269 > 110000
===============================================================================
Compiled by R. P. Brent with assistance from F. Berger, A. Brown, J. Card,
S. Cavallar, T. Charron, C. Curry, B. Dodson, M. Fleuren, T. Granlund, Y. Kida,
H. Kuwakado, A. Lenstra, P. Leyland, N. Lygeros, A. MacLeod, J-C. Meyrignac,
M. Mizony, P. Montgomery, A. Mueller, T. Nokleby, E. Prestemon, M. Quercia,
D. Rusin, R. Silverman, M. Ukai, S. Wagstaff, G. Wambach, M. Wiener,
G. Woltman, A. Yamasaki and P. Zimmermann.
[see champs1.txt for factors of at least 40 decimal digits found to
31 December 1998, champs2.txt for more details, champs98.txt for 1998, etc.]
Last revised 31 December 1999.