Factorization of a 512-bits RSA key using the Number Field Sieve ---------------------------------------------------------------- On August 22, 1999, we found that the 512-bits number RSA-155 = 1094173864157052742180970732204035761200373294544920599091384213147634\ 9984288934784717997257891267332497625752899781833797076537244027146743\ 531593354333897 can be written as the product of two 78-digit primes: 102639592829741105772054196573991675900716567808038066803341933521790711307779 * 106603488380168454820927220360012878679207958575989291522270608237193062808643 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-155 is taken from the RSA Challenge list (see http://www.rsa.com/rsalabs/html/factoring.html). This factorization was found using the Number Field Sieve (NFS) factoring algorithm, and beats the 140-digit record RSA-140 that was set on February 2, 1999, also with the help of NFS [RSA140]. The amount of computer time spent on this new factoring world record is estimated to be equivalent to 8000 mips years. For the old 140-digit NFS-record, this effort was estimated to be 2000 mips years. Extrapolation using the asymptotic complexity formula for NFS would predict approximately 14000 mips years for RSA-155. The gain is caused by an improved application of the polynomial search method used for RSA-140. For information about NFS, see [LL]. For additional information, implementations and previous large NFS factorizations, see [DL, E1, E2, GLM]. Polynomial selection -------------------- The following two polynomials F_1(x,y) = 11 93771 38320 x^5 - 80 16893 72849 97582 y *x^4 - 66269 85223 41185 74445 y^2*x^3 + 1 18168 48430 07952 18803 56852 y^3*x^2 + 745 96615 80071 78644 39197 43056 y^4*x - 40 67984 35423 62159 36191 37084 05064 y^5 F_2(x,y) = x - 3912 30797 21168 00077 13134 49081 y were selected with the help of a polynomial search method developed by Peter Montgomery (Microsoft Research, USA and CWI) and Brian Murphy (The Australian National University, Canberra), which was applied already to RSA-140, and now, even more successfully, to RSA-155. 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 137 decimal digits. Measured in a different way: the pair (F_1, F_2) has a yield of relations approximately 13.5 times that of a random polynomial selection for RSA-155 (the corresponding figure for the polynomial selected for the RSA-140 factorisation is 8). The polynomial selection took approximately 100 MIPS years, which is equivalent to 0.40 CPU years on a 250 MHz SGI Origin 2000 processor (most of the searches were done on such processors). The original polynomial selection code was ported by Arjen Lenstra to use his multiple precision arithmetic package LIP. Brian Murphy, Peter Montgomery, Arjen Lenstra and Bruce Dodson ran the polynomial searches for RSA-155 with this code. The above polynomial emerged from Bruce Dodson's search. Calendar time for the polynomial selection was approximately nine weeks. The Sieving ----------- Sieving was done on about 160 175-400 MHz SGI and Sun workstations, on 8 300 MHz SGI Origin 2000 processors, on about 120 300-450 MHz Pentium II PCs, and on 4 500 MHz Digital/Compaq boxes. The total amount of CPU-time spent on sieving was 35.7 CPU years estimated to be equivalent to approximately 8000 mips years. Calendar time for sieving was 3 1/2 months. For the purpose of comparison, both lattice sieving and line sieving were used. Lattice sieving was introduced by Pollard [P] and the code used is based on the implementation described in [GLM, Cetal]. For the lattice sieve, a factor base bound of 16 777 216 (2^24) was chosen, both for the rational and for the algebraic side. Two large primes were allowed on both sides. Most of the line sieve was carried out with two large primes on both the rational and the algebraic side. The rational factor base consisted of the primes < 44 000 000 and the algebraic factor base of the primes < 110 000 000. Some line sieving allowed three large primes instead of two on the algebraic side. In that case the rational factor base consisted of the primes < 8 000 000 and the algebraic factor base of the primes < 25 000 000. For both sieves the large prime bound 1 000 000 000 was used both for the rational and for the algebraic primes. A total of 124 722 179 relations were generated, 71% of them with lattice sieving (L), 29% with line sieving (C). Among them, there were 39 187 441 duplicates, partially because of the simultaneous use of the two sievers. Sieving was done at eleven different locations with the following contributions: (L: using lattice sieving code from Arjen K. Lenstra C: using line sieving code from CWI) 20.1 % (3057 CPU days) Alec Muffett (L at Sun Microsystems Professional Services, Camberley, UK) 17.5 % (2092 CPU days) Paul Leyland (L,C at Microsoft, Cambridge, UK) 14.6 % (1819) Peter L. Montgomery, Stefania Cavallar (C,L at CWI, Amsterdam) 13.6 % (2222) Bruce Dodson (L,C at Lehigh University, Bethlehem, PA, USA) 13.0 % (1801) Francois Morain and Gerard Guillerm (L,C at Ecole Polytechnique, Palaiseau, France) 6.4 % (576) Joel Marchand (L,C at Ecole Polytechnique/CNRS, Palaiseau, France) 5.0 % (737) Arjen K. Lenstra (L at Citibank, Parsippany, NJ, USA and Univ. of Sydney, Australia) 4.5 % (252) Paul Zimmermann (C at Inria Lorraine and Loria, Nancy, France) 4.0 % (366) Jeff Gilchrist (L at Entrust Technologies Ltd., Ottawa, Canada) 0.65 % (62) Karen Aardal (L at Utrecht University, The Netherlands) 0.56 % (47) Chris and Craig Putnam (L at ?) Calendar time for the sieving was 3.7 months. The relations were collected at CWI and required 3.7 Gbytes of disk space. ^^^ Filtering and linear algebra ---------------------------- The filtering of the data and the building of the matrix were carried out at CWI and took one month. The resulting matrix had 6 699 191 rows, 6 711 336 columns, and weight 417 132 631 (62.27 nonzeros per row). With the help of Peter Montgomery's Cray implementation of the blocked Lanczos algorithm (cf. [M95]) it took 224 CPU hours and 2 Gbytes 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 9 1/2 days. Square root ----------- On August 20-21, 1999, four different square root (cf. [M93]) jobs were started in parallel on four different 300 MHz processors of CWI's SGI Origin 2000, each handling one dependency. One job found the factorisation after 39.4 CPU-hours, the other three jobs found the trivial factorization after 38.3, 41.9, and 61.6 CPU-hours (different CPU times are due to the use of different parameters in the four jobs). Herman te Riele, CWI, August 26, 1999 with the algorithmic and sieving contributors: Stefania Cavallar Bruce Dodson Arjen Lenstra Walter Lioen Peter L. Montgomery Brian Murphy and the sieving contributors: Karen Aardal Jeff Gilchrist Gerard Guillerm Paul Leyland Joel Marchand Francois Morain Alec Muffett Craig and Chris Putnam Paul Zimmermann Acknowledgements are due to the contributors of idle PC and workstation cycles, to the Dutch National Computing Facilities Foundation (NCF) for the use of the Cray-C916 supercomputer at SARA and (in alphabetical order) to Centre Charles Hermite (Nancy, France), Citibank (Parsippany, NJ, USA), CWI (Amsterdam, The Netherlands), Ecole Polytechnique/CNRS (Palaiseau, France), Entrust Technologies Ltd. (Ottawa, Canada), Lehigh University (Bethlehem, PA, USA), the Magma Group of John Cannon at the University of Sydney, the Medicis Center at Ecole Polytechnique (Palaiseau, France), Microsoft Research (Cambridge, UK), Sun Microsystems Professional Services (Camberley, UK), and The Australian National University (Canberra, Australia) for the use of their computing resources. References: ----------- [RSA140]Stefania Cavallar, Bruce Dodson, Arjen Lenstra, Paul Leyland, Walter Lioen, Peter L. Montgomery, Brian Murphy, Herman te Riele, and Paul Zimmermann, Factorization of RSA-140 using the Number Field Sieve, to appear in: Lam Kwok Yan, Eiji Okamoto, and Xing Chaoping, editors, Advances in Cryptology -- Asiacrypt '99, Lecture Notes in Computer Science # xxxx, Springer--Verlag, Berlin, etc., 1999. [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 Here are the P+-1 factorizations of the factors: 102639592829741105772054196573991675900716567808038066803341933521790711307779 p78 102639592829741105772054196573991675900716567808038066803341933521790711307778 2.607.305999. 276297036357806107796483997979900139708537040550885894355659143575473 102639592829741105772054196573991675900716567808038066803341933521790711307780 2.2.3.5.5253077241827. 325649100849833342436871870477394634879398067295372095291531269 106603488380168454820927220360012878679207958575989291522270608237193062808643 p78 106603488380168454820927220360012878679207958575989291522270608237193062808642 2.241.430028152261281581326171. 514312985943800777534375166399250129284222855975011 106603488380168454820927220360012878679207958575989291522270608237193062808644 2.2.3.130637011.237126941204057.10200242155298917871797 28114641748343531603533667478173