---------------------------- 227-digit SNFS factorization ------------------------------------------------ This announcement can be ftp-ed from: ftp://ftp.cwi.nl/pub/herman/SNFSgiants/SNFS-227 ------------------------------------------------
The factorization of the smallest composite Mersenne number without known factor, M751 = 2^751 -1 = N, was completed on January 22, 2002, using the Special Number Field Sieve (SNFS). The sieving was primarily done at CWI, at Lehigh University, the Institute for Pure Math, Bonn University and the Institute for Applied Math, Bonn University; with additional contributions from Arjen Lenstra, Citicorp and Paul Leyland, Microsoft Research. Two notable features as compared to previous large collaborative SNFS factorizations are the use of three distinct sievers (rather than two; the new addition being Jens Franke's lattice siever with rational special primes q) and further exploration of the fast linear algebra provided by parallel Lanczos on the SARA Computing Center's Origin 3800 (an upgrade of the previous standard; our previous program used a single CPU of the 12-processor Cray C90). A Table of current factorization dates is given below. This is the 3rd (200+)-digit SNFS factorization done subsequent to the factorization of RSA-512 (ftp://ftp.cwi.nl/pub/herman/GNFSrecords/GNFS-512). First, we found three prime factors from the 227-digit composite cofactor (2^773+1)/(3*533371), the smallest having 55-digits. Next was M727 = 2^727-1, which we found to have just two prime factors, the smallest with 98-digits (cf. Peter Montgomery's post, for example at http://www.lehigh.edu/~bad0/msg06332.html taken from the Mersenne archive). The present factorization, of the just slightly smaller 227-digit M751 = 2^751-1, is ************** c227 = p1.p2.p3 p1 = 22764024512532445092774588186840266769462045797638178267254980648\ 7 (66 digits) p2 = 64935003199370114500077042183338517573218246028593057485230891498 97 (67 digits) p3 = 80130680840326532624075176541872828138563939790501465580817976318\ 12307901576375946587821853073 (94 digits) ************** TABLE of Factorization Dates: Number 2,773+ 10,211- 2,727- 2,751- RSA-140 RSA-155a RSA-155b RSA-158 Factored by Cabal Cabal Granlund Franke et al. et al. Method SNFS SNFS SNFS SNFS GNFS GNFS GNFS GNFS #decimals 233 211 219 227 140 155 155 158 p sizes 55,71,102 93,118 98,122 66,67,94 70,70 78,78 78,78 73,86 Factored Nov Apr Aug Jan Feb Aug Oct Jan in 2000 1999 2001 2000 1999 1999 2000 2002 For 2,751- we used the two polynomials f(X) = 2X^6 - 1 g(X) = X - 2^125 with common root m = 2^125 (mod N). All relations used had large primes bounded by 10^9 (although some relations were found by sieving with a bound of 4*10^8). The relations found at CWI used large memory line-sieving jobs, with factor base bounds of 110M. Lattice sieving with algebraic special-q was done by Dodson, Lenstra and Leyland, with factor base bounds 16.7M. (These relations are referred to below as "Dodson"'s.) Lattice sieving with rational special-q was done by Franke (who acknowledges the contribution of computing time from members of the scientific computing department at Bonn and useful suggestions by T. Kleinjung for improving the siever code). Franke's initial relations were found with a small sieving region and factor bases; but most were found with a sieving region of 16385x8192 (similar to the region used on the algebraic side), and factor base bounds 32M. Use of three sievers introduces additional opportunity for a single relation to be found more than once, which complicates both reliably determining when sieving is complete and evaluating the relative performance of the sievers. We describe the numbers of relations found so as to clarify this point. First, line sieving produces no self-duplicates, and CWI's total of 24.058 million relations were all distinct. Dodson's relations were filtered at Lehigh to remove duplicates (which occur when a single relation occurs with more than one algebraic special-q in the range of q's that were sieved), with 32.500 million distinct relations. Franke still had data from the recent GNFS 158-digit record occupying disk space, and sent most of his raw data by mail to CWI, on 3 CD's. After removing duplicates (with more than one rational special-q) Franke had 44.442 million distinct relations. We analyzed duplications among these three sets of relations, corresponding to the three sieving programs, a total of 101 million relations. There were a total of 84.314 million distinct relations, which occurred as follows: 13.361 M by CWI only 24.408 M by Dodson only 30.928 M by Franke only 2.100 M by both CWI and Dodson 7.523 M by both CWI and Franke 4.917 M by both Dodson and Franke 1.073 M by all three sieving programs ------- 84.314 M total distinct (exact values available from Peter, there was a perfect match in the counts) which turns out to have been about 10% more than we needed, allowing additional heavy rows to be removed (in the filtering step) before starting the matrix. We observe that, in this instance, Franke's relations (rational q's) duplicated CWI's (line sieving) more than Dodson's (algebraic q's); a phenomenon that may be explained by the small sieving region used to find the initial c. 20% of the relations. A filter program [Stefania Cavallar, Strategies in filtering in the number field sieve, pp. 209-231 in: Wieb Bosma (Ed.), Algorithmic Number Theory (4th International Symposium, ANTS-IV, Leiden, The Netherlands, July 2000), LNCS # 1838, Berlin, Springer, 2000] transformed the 84.3M relations into 5.1 million sets, with 4.9 million ideals of norm > 2 million appearing somewhere with odd exponents. These sets had a combined 28.0 million relations (some appearing in multiple sets), with at most 13 relations per set. After appending extra columns for free relations and extra rows for prime ideals < 2 million (but above 180), the matrix had 5165790 rows and 5185901 columns with 359525164 1's, 69 entries/row. The Block Lanczos program took 64 hours elapsed time on 25 processors, as compared to 25 hours on 25 processors for the M727-matrix. The processors are 500 MHz MIPS R14000. Total calendar time for processing the sieving data and getting the factorization, after its arrival at CWI, was under two weeks. We ran two concurrent copies of the square root program on CWI's 32-processor Origin 2000, each copy using one processor. The first copy got a trivial factorization on its first dependency, later finding the p66 on its second dependency and p67 on its third dependency. This copy took 10.5 hours/dependency plus 3.6 hours for quadratic character tests (35 hours overall). The second copy, which took only 6.1 hours/dependency due to a different tuning parameter, found the p94 three times before the first copy had found the p66. Later the second copy found p94 a fourth time, followed by a trivial factorization and finally p66 (40 hours overall). * P +-1 factors 227640245125324450927745881868402667694620457976381782672549806487 p66 227640245125324450927745881868402667694620457976381782672549806486 2.9.751.294641.p56 227640245125324450927745881868402667694620457976381782672549806488 8.6651821853617.136241126419733160532013 31398595528539042286410894991 6493500319937011450007704218333851757321824602859305748523089149897 p67 6493500319937011450007704218333851757321824602859305748523089149896 8.3.7.17.17.647.751.38273.257021957.2537261620168202723 11028070721134373040809603 6493500319937011450007704218333851757321824602859305748523089149898 2.71.26292652373563702220343453802747.1739226413630785782490582253958377 8013068084032653262407517654187282813856393979050146558081797631812307901576375946587821853073 p94 8013068084032653262407517654187282813856393979050146558081797631812307901576375946587821853072 16.3.751.1433.19777.2111446855467627361.40440513178908580709 5972626530720172492999.15379736065763355855479 8013068084032653262407517654187282813856393979050146558081797631812307901576375946587821853074 2.121.29.6941503.26561393.194251754724023.1047717590961575751282643.p38 Acknowledgments ---------------- We thank the Dutch National Computing Facilities Foundation NCF for providing access to the SGI Origin 3800 at SARA (the Academic Computing Centre Amsterdam); Lehigh University for use of SGI workstations and an SGI Origin 2000; the Institute for Pure Mathematics, Bonn University and the Institute for Applied Mathematics, Bonn University (especially the Scientific Computing Department) for use of a large number of PCs. Bruce Dodson, Lehigh University Jens Franke, Institute for Pure Mathematics, Bonn University Arjen K. Lenstra, Citicorp Paul Leyland, Microsoft Research Peter L. Montgomery, Microsoft Research and CWI Herman te Riele, CWI _________________________________________________________________________ Unsubscribe & list info -- http://www.ndatech.com/mersenne/signup.htm Mersenne Prime FAQ -- http://www.tasam.com/~lrwiman/FAQ-mers
