Anonymous ID: 84141f March 26, 2019, 5:38 p.m. No.5913107   🗄️.is 🔗kun   >>3655

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.