mersenneforum.org RSA-200 factored
 Register FAQ Search Today's Posts Mark Forums Read

 2005-05-09, 16:39 #1 xilman Bamboozled!     "𒉺𒌌𒇷𒆷𒀭" May 2003 Down not across 101010000111002 Posts RSA-200 factored Thorsten Kleinjung has just announced the factorization of a 200--digit number by GNFS. His announcement is copied below. This is impressive! Paul Code: We have factored RSA200 by GNFS. The factors are 35324619344027701212726049781984643686711974001976\ 25023649303468776121253679423200058547956528088349 and 79258699544783330333470858414800596877379758573642\ 19960734330341455767872818152135381409304740185467 We did lattice sieving for most special q between 3e8 and 11e8 using mainly factor base bounds of 3e8 on the algebraic side and 18e7 on the rational side. The bounds for large primes were 2^35. This produced 26e8 relations. Together with 5e7 relations from line sieving the total yield was 27e8 relations. After removing duplicates 226e7 relations remained. A filter job produced a matrix with 64e6 rows and columns, having 11e9 non-zero entries. This was solved by Block-Wiedemann. Sieving has been done on a variety of machines. We estimate that lattice sieving would have taken 55 years on a single 2.2 GHz Opteron CPU. Note that this number could have been improved if instead of the PIII- binary which we used for sieving, we had used a version of the lattice-siever optimized for Opteron CPU's which we developed in the meantime. The matrix step was performed on a cluster of 80 2.2 GHz Opterons connected via a Gigabit network and took about 3 months. We started sieving shortly before Christmas 2003 and continued until October 2004. The matrix step began in December 2004. Line sieving was done by P. Montgomery and H. te Riele at the CWI, by F. Bahr and his family. More details will be given later. F. Bahr, M. Boehm, J. Franke, T. Kleinjung
 2005-05-09, 17:03 #2 Mystwalker     Jul 2004 Potsdam, Germany 11001111112 Posts They just looped over RSA-640... MANY CONGRATULATIONS TO F. Bahr, M. Boehm, J. Franke, T. Kleinjung!
 2005-05-09, 18:58 #3 ValerieVonck     Mar 2004 Belgium 292 Posts Yep congrats!! Over wich RSA challenge number we are talking about? Or is this not correct??? Last fiddled with by ValerieVonck on 2005-05-09 at 18:58
2005-05-09, 19:24   #4
Mystwalker

Jul 2004
Potsdam, Germany

3×277 Posts

Good question...

The challenge website only states RSA-640 (193 digits) and RSA-704 (212 digits).

One possibility is that RSA-200 belongs to the "old" challenge:

Quote:
 The largest previously factored challenge number is RSA-160 from the "old" challenge, where numbers were designated by their length in decimal digits rather than bits; RSA-160 is 530-bit number.

2005-05-09, 19:59   #5
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

2A1C16 Posts

Quote:
 Originally Posted by Mystwalker Good question... The challenge website only states RSA-640 (193 digits) and RSA-704 (212 digits). One possibility is that RSA-200 belongs to the "old" challenge:
That's the one. It has 200 digits and factors into two primes of 100 digits each.

Paul

 2005-05-09, 20:06 #6 akruppa     "Nancy" Aug 2002 Alexandria 46438 Posts Very impressive. Any idea why they didn't do RSA-640 first? Perhaps they expected that someone else (i.e. Kida) might factor that one before they could? Alex
 2005-05-09, 20:41 #7 trilliwig     Oct 2004 tropical Massachusetts 3×23 Posts Wow, that is an impressive achievement. We can mark another milestone knocked over, and it was considerate of Kleinjung et al to make it a conveniently easy-to-remember number. The only thing that would be interesting left out of the summary was details of polynomial selection. Sam
 2005-05-09, 21:27 #8 JHansen     Apr 2004 Copenhagen, Denmark 22×29 Posts Full list of RSA numbers Here is the full list of the RSA Challenge numbers: RSA Number List -- Cheers, Jes
2005-05-10, 07:39   #9
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

22×5×72×11 Posts

Quote:
 Originally Posted by akruppa Very impressive. Any idea why they didn't do RSA-640 first? Perhaps they expected that someone else (i.e. Kida) might factor that one before they could? Alex
I suspect that the prize money may have had something to do with it.

Distributing the money for rsa-576 was a political and logistical nightmare (as far as I could tell) and I wouldn't be at all surprised if the bad memories of that occasion influence the choice.

Paul

 2005-05-10, 10:12 #10 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts Kinda odd, considering that the prize money was meant as an incentive... The news has hit papers all over by now. These people http://www.krone.at/index.php?http:/...__30327/hxcms/ seem to have got something wrong, although they could argue that the number in the title has been completely factored as well Alex
 2005-05-10, 12:53 #11 BotXXX     Aug 2003 Europe 2·97 Posts Congratz, and indeed distributing the prize money can be a difficult matter. Especially when you are dealing with different countries (and their tax/donation laws) and with institutions (like universities or companys) that gave the possibility to use their hardware/infrastructure. How would you divide the money and so on. Better would to donate it to charity, but all participants should have to agree on that. But on the factoring is big. very very big. Congratz

 Similar Threads Thread Thread Starter Forum Replies Last Post ryanp Factoring 6 2013-11-26 09:33 aketilander Factoring 4 2012-08-08 18:09 unconnected Factoring 31 2010-06-26 04:07 Raman Factoring 4 2010-04-01 13:57 ewmayer Math 5 2003-05-14 15:08

All times are UTC. The time now is 11:38.

Sun Aug 1 11:38:29 UTC 2021 up 9 days, 6:07, 0 users, load averages: 1.09, 1.25, 1.24