From Herman.te.Riele@cwi.nl Thu Feb 4 17:55:08 1999 Date: Thu, 4 Feb 1999 07:45:42 -0500 From: Herman.te.Riele@cwi.nl To: NMBRTHRY@LISTSERV.NODAK.EDU Subject: factorization of RSA-140 Factorization of RSA-140 using the Number Field Sieve ----------------------------------------------------- On February 2, 1999, we found that RSA-140 = 2129024631825875754749788201627151749780670396327721627823338321538194\ 9984056495911366573853021918316783107387995317230889569230873441936471 can be written as the product of two 70-digit primes: 3398717423028438554530123627613875835633986495969597423490929302771479 * 6264200187401285096151654948264442219302037178623509019111660653946049 Primality of the factors was proved with the help of two different primality proving codes. An Appendix gives the prime decompositions of p +- 1. The number RSA-140 is taken from the RSA Challenge list (http://www.rsa.com/rsalabs/html/factoring.html). This factorization was found using the Number Field Sieve (NFS) factoring algorithm, and beats the 130-digit record that was set on April 10, 1996, also with the help of NFS [Cetal]. The amount of computer time spent on this new 140-digit NFS-record is prudently estimated to be equivalent to 2000 mips years. For the old 130-digit NFS-record, this effort is estimated to be 1000 mips years. For both numbers, lower "could-have-done-it-in" estimates, based on a better use of the lattice siever, are: 500 mips years for RSA-130 and 1500 mips years for RSA-140. For information about NFS, see [LL]. For additional information, implementations and previous large NFS factorizations, see [DL, E1, E2, GLM]. We used the two polynomials F_1(x,y) = 43 96820 82840 x^5 + 39031 56785 38960 y *x^4 - 7387 32529 38929 94572 y^2*x^3 - 19 02715 324374 29887 14824 y^3*x^2 - 6 34410 25694 46461 79139 30613 y^4*x + 31855 39170 71474 35039 22235 07494 y^5 F_2(x,y) = x - 3 44356 57809 24253 69517 79007 y . They were selected with the help of a new polynomial search method developed by Peter Montgomery and Brian Murphy (The Australian National University, Canberra). The polynomial F_1(x,y) was chosen to have a good combination of two properties; being unusually small over its sieving region and having unusually many roots modulo small primes (and prime powers). The effect of the second property alone gives F_1(x,y) a smoothness yield comparable to that of a polynomial chosen at random for an integer of 121 decimal digits. The selection took 2000 CPU hours on four 250 MHz SGI Origin 2000 processors at CWI. Calendar time for the polynomial selection was four weeks. Sieving was done on about 125 SGI and Sun workstations running at 175 MHz on average, and on about 60 PCs running at 300 MHz on average. The total amount of CPU-time spent on sieving was 8.9 CPU years. For the purpose of comparison, two sieving methods were used: lattice sieving and line sieving. Lattice sieving was introduced by Pollard [P] and the code used is based on the implementation described in [GLM, Cetal]. For the lattice sieving, a rational factor base of 250 000 elements (the primes <= 3 497 867) and an algebraic factor base of 800 000 elements (ideals of norm <= 12 174 433) were chosen. For the line sieving, different factor base bounds were chosen, namely: a rational factor base consisting of the primes < 8 000 000 and an algebraic factor base with the primes < 16 777 215 = 2^24 - 1. For both sieves the large prime bounds were: 500 000 000 for the rational primes and 1 000 000 000 for the algebraic primes. A total of 66 933 395 relations were generated, 55% of them with lattice sieving (L), 45% with line sieving (C). Among them, there were 10 327 897 duplicates, partially because of the simultaneous use of the two sievers. Sieving was done at five different locations with the following contributions: 36.8 % Peter L. Montgomery, Stefania Cavallar, Herman J.J. te Riele, Walter M. Lioen (C,L at CWI, Amsterdam, The Netherlands) 28.8 % Paul C Leyland (L at Microsoft Research Ltd, Cambridge, UK) 26.6 % Bruce Dodson (C,L at Lehigh University, Bethlehem, PA, USA) 5.4 % Paul Zimmermann (L at Inria Lorraine and Loria, Nancy, France) 2.5 % Arjen K. Lenstra (L at Citibank, Parsippany, NJ, USA, and at the University of Sydney, Australia) Sieving started the day before Christmas 1998 and was completed one month later. The relations were collected at CWI and required 3.7 Gbytes of memory. The filtering of the data and the building of the matrix were carried out at CWI and took one calendar week. The resulting matrix had 4 671 181 rows and 4 704 451 columns, and weight 151 141 999 (32.36 nonzeros per row). With the help of Peter Montgomery's Cray implementation of the blocked Lanczos algorithm (cf. [M95]) it took almost 100 CPU hours and 810 Mbytes of central memory on the Cray C916 at the SARA Amsterdam Academic Computer Center to find 64 dependencies among the rows of this matrix. Calendar time for this job was five days. During February 1-2, 1999, four different square root (cf. [M93]) jobs were started in parallel on four different 250 MHz processors of CWI's SGI Origin 2000, each handling one dependency. After 14.2 CPU hours, one of the four jobs stopped, giving the two prime factors of RSA-140. Two others also expired with the two prime factors after 19 CPU hours (due to different input parameter choices). Only one of the four jobs expired with the trivial factors. Herman te Riele, CWI, February 3, 1999 with Stefania Cavallar Bruce Dodson Arjen Lenstra Paul Leyland Walter Lioen Peter Montgomery Brian Murphy Paul Zimmermann Acknowledgements are due to the contributors, and to the Dutch National Computing Facilities Foundation (NCF) for the use of the Cray-C916 supercomputer at SARA. [Cetal] James Cowie, Bruce Dodson, R.-Marije Elkenbracht-Huizing, Arjen K. Lenstra, Peter L. Montgomery and Joerg Zayer, A world wide number field sieve factoring record: on to 512 bits, pp. 382-394 in: Kwangjo Kim and Tsutomu Matsumoto (editors), Advances in Cryptology - Asiacrypt '96, Lecture Notes in Computer Science # 1163, Springer-Verlag, Berlin, 1996. [DL] B. Dodson, A.K. Lenstra, NFS with four large primes: an explosive experiment, Proceedings Crypto 95, Lecture Notes in Comput. Sci. 963, (1995) 372-385. [E1] R.-M. Elkenbracht-Huizing, Factoring integers with the Number Field Sieve, Doctor's Thesis, Leiden University, 1997. [E2] R.-M. Elkenbracht-Huizing, An implementation of the number field sieve, Exp. Math. 5, (1996) 231-253. [GLM] R. Golliver, A.K. Lenstra, K.S. McCurley, Lattice sieving and trial division, Algorithmic number theory symposium, Proceedings, Lecture Notes in Comput. Sci. 877, (1994) 18-27. [LL] A.K. Lenstra, H.W. Lenstra, Jr., The development of the number field sieve, Lecture Notes in Math. 1554, Springer- Verlag, Berlin, 1993 [M93] Peter L. Montgomery, Square roots of products of algebraic numbers, in Proceedings of Symposia in Applied Mathematics, Mathematics of Computation 1943-1993, Vancouver, 1993, Walter Gautschi, ed. [M95] Peter L. Montgomery, A block Lanczos algorithm for finding dependencies over GF(2), Proceedings Eurocrypt 1995, Lecture Notes in Comput. Sci. 921, (1995) 106-120. [P] J.M. Pollard, The lattice sieve, pages 43-49 in [LL]. Appendix -------- 3398717423028438554530123627613875835633986495969597423490929302771479 3398717423028438554530123627613875835633986495969597423490929302771478 2 7 7649 435653 396004811 183967535370446691250943879126698812223588425357931 3398717423028438554530123627613875835633986495969597423490929302771480 2 2 2 3 3 5 13 8429851 33996935324034876299 2534017077123864320746970114544624627539 6264200187401285096151654948264442219302037178623509019111660653946049 6264200187401285096151654948264442219302037178623509019111660653946048 2 2 2 2 2 2 61 135613 3159671789 3744661133861411144034292857028083085348933344798791 6264200187401285096151654948264442219302037178623509019111660653946050 2 3 5 5 389 6781 982954918150967 16106360796654291745007358391328807590779968869