Factorization of RSA-140 using the number field sieve
On February 2, 1999, we completed the factorization of the 140--digit number RSA--140 with the help of the Number Field Sieve factoring method (NFS). This is a new general factoring record. The previous record was established on April 10, 1996 by the factorization of the 130--digit number RSA--130, also with the help of NFS. The amount of computing time spent on RSA--140 was roughly twice that needed for RSA--130, about half of what could be expected from a straightforward extrapolation of the computing time spent on factoring RSA--130. The speed-up can be attributed to a new polynomial selection method for NFS which will be sketched in this paper. par The implications of the new polynomial selection method for factoring a 512--bit RSA modulus are discussed and it is concluded that 512--bit (= 155--digit) RSA moduli are easily and realistically within reach of factoring efforts similar to the one presented here.
|Numerical Algorithms and Problems (acm F.2.1)|
|Factorization (msc 11Y05), Factorization; primality (msc 11A51)|
|Life Sciences (theme 5), Energy (theme 4)|
|Modelling, Analysis and Simulation [MAS]|
Cavallar, S.H, Dodson, B, Lenstra, A.K, Leyland, P.C, Lioen, W.M, Montgomery, P.L, … Zimmermann, P. (1999). Factorization of RSA-140 using the number field sieve. Modelling, Analysis and Simulation [MAS]. CWI.