IP: First factorization of a "hard" 512-bit integer

[David Farber <farber@cis.upenn.edu>]

>Date: Thu, 26 Aug 1999 14:22:28 -0400
>From: denning@cs.georgetown.edu (Dorothy Denning)
>
>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:
>
>1026395928297411057720541965739916759007165678080380668033419335217907113077
>79
>*
>1066034883801684548209272203600128786792079585759892915222706082371930628086
>43
>
>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:
>
>1026395928297411057720541965739916759007165678080380668033419335217907113077
>79
>        p78
>1026395928297411057720541965739916759007165678080380668033419335217907113077
>78
>        2.607.305999.
>
>276297036357806107796483997979900139708537040550885894355659143575473
>1026395928297411057720541965739916759007165678080380668033419335217907113077
>80
>        2.2.3.5.5253077241827.
>        325649100849833342436871870477394634879398067295372095291531269
>
>1066034883801684548209272203600128786792079585759892915222706082371930628086
>43
>        p78
>1066034883801684548209272203600128786792079585759892915222706082371930628086
>42
>        2.241.430028152261281581326171.
>        514312985943800777534375166399250129284222855975011
>1066034883801684548209272203600128786792079585759892915222706082371930628086
>44
>        2.2.3.130637011.237126941204057.10200242155298917871797
>        28114641748343531603533667478173