Date: Tue, 29 Jul 2003 18:55:16 -0400
Reply-To: Bruce Dodson
Sender: Number Theory List
From: Bruce Dodson
Subject: 301-digit integer factored: ecm record 57-digit factor
301-digit integer factored: ecm record 57-digit factor
^^^^^^^^^^^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^^^^^^^^^^^^
- B. Dodson
I'm writing to report a new factoring record for the Elliptic
Curve Method (ecm), a 57-digit prime factor, p57, of the Mersenne
number M997 = 2^997-1, where
p57 = 167560816514084819488737767976263150405095191554732902607.
M997 was a 301-digit composite without known factor, and as the
cofactor is also prime, this result completes a factorization that
would otherwise have required many cpu-years using the (special)
number field sieve. This is the 3rd number factored from a list
of five identified by George Woltman, as being Mersenne numbers
Mn = 2^n-1, with prime exponent n meeting the Cunningham bound
n < 1200, but with no known factors. There is a minor interest
from the project for locating Mersenne primes using the Lucas-Lehmer
primality test (http://www.mersenne.org), since (for large n)
finding a small prime factor saves an expensive LL-test.
The other two factored numbers (of the five) are M727, with
smallest prime factor having 98-digits; and M809, with smallest
prime factor having 61-digits. Each of these actually was factored
by an extended snfs sieving effort (by Dodson and A. K. Lenstra;
respectively by Franke and Kleinjung: the present record for snfs
factorizations). For each of these numbers the matrix step was run
by CWI under a grant on the SARA computing center's SGI Origin 3800
using Montgomery's parallel Lanczos method (the matrix for M727
having 3.8 million rows/columns; for M809 there were 8.9 million
rows/columns). The two remaining are M971 and M1061. Regarding the
present status of sieving methods, we expect a 1024-bit snfs
factorization to precede a 768-bit RSA-key being broken by gnfs.
While the Cunningham objective of factoring all of the Mersenne
numbers, n < 1200 (among many other such numbers) has only a side
relation to the Mersenne project, this is the second ecm record set
using Woltman's program "Prime95", which makes use of the number
b^n-1 having base b=2. The first was a 53-digit prime factor of
M667, replacing an earlier record 49-digit factor. Those factors
occurred during an intensive effort in 1998 to find the first ecm
factor of 50-digits or more, set by Brent as an objective for ecm
with "a second step", shortly after H. W. Lenstra's introduction of
the method. There have been intermediate ecm record factors with 54-
digits and 55-digits; but the present 2-digit increase to 57-digits
seems to be regarded as an indication that we should now expect to
see a 60-digit factor found by ecm, perhaps within two or three
years.
Regarding the computation that produced the 57-digit factor,
it occurred very early in a search intended to remove 50-digit
prime factors, using first step limit 44 million, second step
limit 4.29 billion (i.e., c. 100 times the first step limit).
We expect to need to check 19300 curves with these limits to
have a probability of 1-1/e (=63.2%) of finding a 50-digit
factor (after which, we should increase limits, to look for
a factor with 55-digits, say). The above factor was found
on just the 261st curve checked, only five days of cpu-time.
Perhaps a better indication of the effort spent is that the ecm
program was running on an input file with 11 hard numbers, on
three 1.7MHz Pentium IV's, used for 4 months: approximately 1
cpu-year. The numbers M971 and M997 were added at the start of
the 4th month. If the full cpu-year had been spent on M997,
about 18000 curves would have been completed.
The elliptic curves used by the program are all 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, and the parameter sigma is chosen at
random. The lucky value sigma = 6329517009540700 was selected
on June 21st. For unlucky sigmas, the procedure first computes
a sequence of points Ri = qi*R(i-1), where qi runs through prime
powers < 44M, R0 = (x1,y1). The 2nd step starts with the point
R resulting at the end of the first step, then repeatedly computes
points Sj = pj*R, where pj ranges over primes 44M < pj < 4290M.
When this procedes un-eventfully, the curve fails (for these bounds),
and we go on to the next curve. These elliptic curve additions
depend upon taking inverses in the ring of integers modulo the
composite M997 (since p57 is un-known), and a factor is found when
the group operations fail, i.e., when there is a nontrivial gcd with
M997. In particular, a prime "p" is found when the order of the
elliptic curve (mod p) has only small prime factors, except for one
large prime factor (where "small" and "large" refer to the 1st and
2nd step bounds). The order of this elliptic curve (mod p57) can be
found using Magma (which has effective point-counting; and used under
a minute of cputime) as
8*3*7*59*499*4787*42787*98317*
5721853*6024911*18448453*33587233*
78756287
with four big step-one factors, up to 33.58M < 44M, and a rather
small step 2 factor 44M < 78.7M < 2*44M << 4290M. Factors of the
group orders p57 -1 and p57+1 are given below; and (as usual)
indicate that neither the (p-1)- nor the (p+1)-method could have
found this factor.
The ECMNET page (http://www.loria.fr/~zimmerma/records/ecmnet.html)
suggests that to have a 63.2% probability of finding a known 55-digit
prime factor one may expect to try 49000 curves with first limit
110 million (an additional 6.8 cpuyears on the pc's used above). No
number has actually been the target of such a search, much less a
large sieving candidate for which the runtime required would represent
an efficient balance of effort between ecm pretest and sieving. As
removing 55-digit factors (to 80% probability, say) becomes the
standard ecm pretest (rather than the current objective of removing
50-digit factors), several ecm records above 60-digits ought to
occur.
While anyone with a spare cpu-year might try looking for a new
record ecm factor, the above snfs factorizations suggest caution in
devoting the entire effort to a single hard target. The present
worst-case for ecm is the 211-digit cofactor of the repunit R223 =
(10^223-1)/9 = 111 ... 111 (223 ones), which factored as a product
of 2 primes, the smaller of which had 105-digits (July 6, 2003,
Dodson/A. K. Lenstra/Leyland). At the other extreme, for the
cabal factorization of P773 = 2^773+1 (the first 768-bit snfs),
we had three prime factors, 55-digits, 71-digits and 102-digits.
Applying present standards to this factorization from 3 years ago,
we might have spent more time in ecm pretesting.
The current status of distributed sieving may be found at
http://www.nfsnet.org, which may shortly start on one of the
other 11 input numbers, M811 = 2^811-1. Further Cunningham
numbers having prime exponent without known (non-algebraic) factors
are collected below (there seem to be just 16, aside from the 2
Mersenne numbers).
Acknowledgements are due to Paul Zimmermann, Richard Brent and
Peter Montgomery. References are to active distributed computing
sites.
- Dept Math, Lehigh University, July 13th 2003 (revised July 25)
----------------------
----------------------
p57-1:
2*997*84032505774365506263158359065327557876176124149815899
p57+1:
16*27*1783*43753*524345539327*19629715997363*483056519006311797181
--------
Hardest Cunningham numbers (Cn denotes a composite with n-digits):
(2^n+1)/3, for n = 827 and 1123 (C249 and C338) (from Pn=2^n+1, n odd,
divisible by 3)
(3^n+1)/4, for n = 491 and 499 (C234 and C238)
(5^n-1)/4, for n = 349 (C244)
(5^n+1)/6, for n = 383 (C267)
(6^n-1)/5, for n = 353 (C274)
(6^n+1)/7, for n = 257 (C200)
(7^n-1)/6, for n = 353 and 379 (C298 and C320)
(7^n+1)/8, for n = 313 (C264)
Rn = (10^n-1)/9, for n = 263 and 311 (C263 and C311)
(10^n+1)/11, for n = 367 (C366)
(12^n-1)/11, for n = 241 (C260) [n=197, C212 having just been
factored by nfsnet]
(12^n+1)/13, for n = 271 (C292)
-------------------------------------------------------
_________________________________________________________________
Back to: Top of message | Previous page | Main NMBRTHRY page
_________________________________________________________________
Powered by LISTSERV(R) CataList - online list search Back to the
LISTSERV home page at LISTSERV.NODAK.EDU.