Factorization of RSA-155
Edit Page
Report
Scan day: 09 February 2014 UTC
46
Virus safety - good
Description: Announcement of factorization of a 512-bit RSA key using the General Number Field Sieve (GNFS).
(August 22, 1999)
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)
Size: 2048 chars
Contact Information
Email: —
Phone&Fax: —
Address: —
Extended: —
WEBSITE Info
| Page title: | |
| Keywords: | |
| Description: | |
| IP-address: | 50.87.151.148 |
WHOIS Info
| NS | Name Server: NS2539.HOSTGATOR.COM Name Server: NS2540.HOSTGATOR.COM |
| WHOIS | Status: clientTransferProhibited |
| Date | Creation Date: 17-mar-2000 Expiration Date: 17-mar-2014 |