Path: ns1.cc.lehigh.edu!netnews.cc.lehigh.edu!netnews.upenn.edu!newsserver.jvnc.
net!howland.reston.ans.net!wupost!uwm.edu!rutgers!walter!jordan!lenstra
From: lenstra@jordan.bellcore.com (Arjen Lenstra)
Newsgroups: sci.crypt
Subject: Factorization of RSA-120
Message-ID: <1993Jun11.191436.7505@walter.bellcore.com>
Date: 11 Jun 93 19:14:36 GMT
Sender: news@walter.bellcore.com
Organization: Bellcore
Lines: 78
Nntp-Posting-Host: jordan.bellcore.com

At 18:06:23 EDT on June 9, 1993, we found that

RSA-120 = 22701048129543736333425996094749366889587533646608478003817325824\
          7009162675779735389791151574049166747880487470296548479
        = 327414555693498015751146303749141488063642403240171463406883 *
          693342667110830181197325401899700641361965863127336680673013

RSA-120 was the smallest unfactored number on the RSA Challenge List.
It has 120 digits; its two prime factors both have 60 digits.

This is a new general purpose factoring record, beating the old 116-digit
record that was set in January 1991, more than two years ago.

The factorization was found using the double large prime multiple
polynomial variation of the quadratic sieve factoring method. The
sieving took approximately 830 mips years and was carried out by
Thomas Denny, Bruce Dodson, Arjen Lenstra, Walter Lioen, Mark Manasse
and Herman te Riele on machines at Saarbruecken University, Lehigh
University, Bellcore, CWI Amsterdam, and DEC Systems Research Center.
Three quarters of the sieving was done on workstations, the rest was
done on Bellcore's MasPar, which also took care of the final matrix
reduction.

Some factoring details:
 In our `factoring by email' work we often used, on purpose, suboptimal
parameter choices to keep the sieving program reasonably small, and
to minimize the amount of email flowing into DEC SRC. For the present
factorization, however, we tried to use optimal parameter choices. This
led to an unusually large factor base (245810 elements) and a larger
large prime bound (effectively 2^30, instead of the usual 10^8). As a
result we collected more than 5 million relations, 1175252338 bytes of
data. We found 48665 full relations and 203557 combinations among 5056835
partial and partial partial relations; only 653899 of these 5056835
relations were actually useful, i.e., occurred in a combination. The
entire relations collection step was done over a period of 82 days,
starting on March 18, 1993.
 The resulting sparse 252222x245810 bit-matrix was reduced to a dense
89304x89088 bit-matrix using structured Gaussian elimination. This took
15 hours on a sparc10 workstation, 10 of which were needed to build
the 994489344 byte dense matrix. The reduction of the dense matrix
was done in core on Bellcore's 16K MasPar: 13 minutes to read the matrix
and 4 hours to do the reduction. The second dependency produced the above
factorization.
 From a preliminary analysis of our data it follows that our choice of
factor base size was indeed close to optimal, and that the larger large
primes were indeed worth the trouble (of dealing with large amounts of
data flowing over the net and excessively large data files). A complete
analysis will appear within the next few months (ask lenstra@bellcore.com
for a copy).
 The approximated run time of 830 mips years given above was derived
as follows: the MasPar produces on average 480 full relations per CPU-day.
Producing 48665 fulls would require 48665/480 = 101 MasPar CPU-days.
One CPU-year on the MasPar is approximately 3000 mips years, so this leads
to the estimated 3000*(101/365) = 830 mips years. This estimate is
too pessimistic for various reasons that will be explained in the paper.
This run time might be compared to the current record factorization of
a special number (2^523-1) which took 22 MasPar CPU-days, i.e., approximately
180 mips years.

Four related factorizations:

327414555693498015751146303749141488063642403240171463406883 - 1 =
2*19*23*173*191*20207133825867205597523477*561051027433723110582599363

327414555693498015751146303749141488063642403240171463406883 + 1 =
2*2*3*3*9094848769263833770865175104142819112878955645560318427969

693342667110830181197325401899700641361965863127336680673013 - 1 =
2*2*673*9500104961*11317677666073*2395450201344737432933763488281637

693342667110830181197325401899700641361965863127336680673013 + 1 =
2*3*262916620273*84600061024799*66760768425507137*77819176795216231

These factorizations demonstrate that the factors of RSA-120 are
inaccessible by the p+-1 factoring methods, unless one uses a first
step limit of 7.8*10^16 for p+1.

Arjen Lenstra