From: Bill Stewart <stewarts@ix.netcom.com>
Date: Mon, 15 Apr 1996 20:07:36 +0800
To: cypherpunks@toad.com
Subject: RSA-130 Falls to NFS - Lenstra Posting to sci.crypt.research
Message-ID: <199604150519.WAA09619@toad.com>
MIME-Version: 1.0
Content-Type: text/plain


From: alenstra@fwi.uva.nl (A. Lenstra)
Newsgroups: sci.crypt.research
Subject: new factorization record
Date: 14 Apr 1996 10:35:20 GMT
Organization: FWI, University of Amsterdam, Bellcore
Lines: 189
Message-ID: <4kqkd8$g37@net.auckland.ac.nz>
Summary: factorization of RSA-130 using the Number Field Sieve
Keywords: factoring, Number Field Sieve, RSA


On April 10, 1996, we found that
 
RSA-130 = 18070820886874048059516561644059055662781025167694013491701270214\
          50056662540244048387341127590812303371781887966563182013214880557
 
has the following factorization
 
RSA-130 = 39685999459597454290161126162883786067576449112810064832555157243
        * 45534498646735972188403686897274408864356301263205069600999044599
 
This factorization was found using the Number Field Sieve (NFS) factoring
algorithm, and beats the 129-digit record that was set on April 2, 1994,
by the Quadratic Sieve (QS) factoring algorithm (cf. [AGLL]). The amount
of computer time spent on this new 130-digit NFS-record is only a fraction
of what was spent on the old 129-digit QS-record (see below for details).
For information about NFS, see [LL]. For additional information,
implementations and previous large NFS factorizations, see [BLZ, DL, E, GLM].
 
We used the polynomial
 
     5748,30224,87384,05200 X^5 +  9882,26191,74822,86102 X^4
  - 13392,49938,91281,76685 X^3 + 16875,25245,88776,84989 X^2
  +  3759,90017,48552,08738 X   - 46769,93055,39319,05995
 
and its root 125,74411,16841,80059,80468 modulo RSA-130. This polynomial
was selected from a list of 14 candidates provided by Scott Huddleston,
after extensive sieving experiments carried out by Joerg Zayer at the
University of Saarland.
 
Sieving was done on a great variety of workstations at many different
locations:
        28.37% by Bruce Dodson (Lehigh University)
        27.77% by Marije Elkenbracht-Huizing (CWI, Amsterdam)
        19.11% by Arjen K. Lenstra (Bellcore)
        17.17% by contributors to the www-factoring project (organized by
                  Jim Cowie, Wojtek Furmanski, and Arjen Lenstra, among others)
         4.36% by Matt Fante (IDA)
         1.66% by Paul Leyland (Oxford University)
         1.56% by Damian Weber (University of Saarland)
 
Except for a relatively small part of the contribution of the CWI and
the entire contribution by the University of Saarland, all contributors
used the NFS sieving program that was developed at Bellcore. This program
uses `lattice sieving with sieving by vectors' as introduced by Pollard
in [P], and is based on the implementation described in [GLM]. The main
difference is the more liberal use of `special q-primes' that define the
lattices (see also [E]). Unlike [GLM], these special q's do not necessarily
belong to the factor base (as is the case in [P]); this idea can also be
found in [B].  Another difference is the more liberal interpretation of
the factor base sizes, which results in a much more flexible memory usage.
 
These changes allowed us to run the sieving program in parallel on almost
any number of processors, as long as they have at least about 6 megabytes
of memory. This was exploited in the Web-based sieving effort, which used
a collection of CGI scripts ("FAFNER", from Cooperating Systems Corporation)
to automate and coordinate the flow of tasks and relations within the
globally distributed network of anonymous sieving clients. As a consequence
almost any user of the Web can contribute to future, larger factoring efforts,
simply by a few appropriate mouse clicks.
 
The changes also made it hard to estimate how much time was spent on the
sieving stage, because the performance of the siever strongly depends
on the amount of memory it gets. We can say, however, that we would have
spent about 500 mips years (i.e., 10% of the computing time spent on the
129-digit QS-record) if we had done all the sieving on average
workstations with at least 24 megabytes of memory.
 
Sieving started in September 1995, initially on a very limited number of
workstations. The Web-based sieving started relatively late, in December
1995. Relations were collected and merged and duplicates were removed at
Bellcore. On Jan 14, 1996, we had 56,515,672 unique relations. In
uncompressed ASCII format, with only the primes >2000000 listed per
factorization, storage of the relations required more than 3.5 gigabytes.
With a rational factor base of 250,001 elements (the primes <= 3,497,867)
and an algebraic factor base of 750,001 elements (ideals of norm <=
11,380,951), the breakdown of full and partial relations is as follows.
 
\ number of prime ideals of norm > 11,380,951:
 \________        0        1        2        3        4        5        6
number of \
rational   \_____________________________________________________________
primes >   |
3,497,867  |
           |
      0    |  48400   479737  1701253  1995537     6836      403        9
      1    | 272793  2728107  9617073 11313254    39755     2212       44
      2    | 336850  3328437 11520120 13030845    56146     3214       71
      3    |   1056     9022    24455        0        0        0        0
      4    |      3        9       31        0        0        0        0
 
The first successful dependency used 4143834 relations, of which 3506 were
free relations. The breakdown of large prime ideals amongst the other
contributing relations is as follows.
 
 
      0    |  24242   154099   330738   255742     1054       52        1
      1    |  75789   443647   885136   648148     2734      164        2
      2    |  56326   300369   565605   389046     1923      131        4
      3    |    182      776     1105        0        0        0        0
      4    |      2        4        7        0        0        0        0
 
 
Once every week during the collection the cycles were counted at Bellcore.
The final collection of 56,467,272 relations with one or more large primes
generated 2,844,859 cycles. In these cycles 18,830,237 (33.3%) of the
partial relations occurred (i.e., were useful). As in our previous NFS
factorizations, we witnessed an explosion in the number of cycles, with
first a sharp increase in the number of useful relations, followed by a
sudden growth of the number of cycles:
 
        # partials      # usefuls       # cycles
        41,319,347          47,660         16,914
        45,431,262       8,214,349        224,865
        53,282,421      11,960,120        972,121
        56,467,272      18,830,237      2,844,859
 
Using the approach sketched in [DL], these data resulted in a
3,504,823 x 3,516,502 matrix of total weight 138,690,744 (on
average 39.4 entries per column). Using Peter Montgomery's Cray
implementation of his blocked Lanczos algorithm (cf. [M95]), it
took 67.5 CPU-hours and 700 Mbyte central memory on the Cray-C90
at the SARA Computer Center in Amsterdam to do the linear algebra.
This resulted in 18 useful dependencies. These were processed on
1 processor of an SGI Challenge (150 MHz R4400SC processors) using
Peter Montgomery's square root program (cf. [M93]), which took 49.5
hours per dependency (with initial numerator and denominator of
approximately 9.7 million decimal digits). The factorization was
found by the third dependency.
 
It is likely that slightly more sieving (and therefore more partials)
would have led to substantially smaller (and easier) matrix and square
root problems.
 
Arjen K. Lenstra, Bellcore, April 11, 1996
 
with    Jim Cowie
        Marije Elkenbracht-Huizing
        Wojtek Furmanski
        Peter L. Montgomery
        Damian Weber
        Joerg Zayer
 
Acknowledgements are due to the contributors, and to the Dutch
National Computing Facilities Foundation (NCF) for the use of
the Cray-C90 supercomputer.
 
 
[AGLL]  D. Atkins, M. Graff, A.K. Lenstra, P.C. Leyland, THE MAGIC
        WORDS ARE SQUEAMISH OSSIFRAGE, Proceedings Asiacrypt'94,
        Lecture Notes in Comput. Sci. 917, (1995) 263-277.
 
[B]     D.J. Bernstein, The multiple-lattice number field sieve, Chapter 3
        of Ph.D. thesis, ftp://koobera.math.uic.edu/pub/papers/mlnfs.dvi.
 
[BLZ]   J. Buchmann, J. Loho, J. Zayer, An implementation of the general
        number field sieve, Proceedings Crypto'93, Lecture Notes in
        Comput. Sci. 773, (1994) 159-165.
 
[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.
 
[E]     R.M. Elkenbracht-Huizing, An implementation of the number
        field sieve, Technical Report NM-R9511, Centrum voor
        Wiskunde en Informatica, Amsterdam, 1995. To appear in
        Experimental Mathematics
 
[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].
#					Thanks;  Bill
# Bill Stewart, stewarts@ix.netcom.com, +1-415-442-2215