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.