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.