20050509, 16:39  #1 
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
2·3·29·67 Posts 
RSA200 factored
Thorsten Kleinjung has just announced the factorization of a 200digit 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 nonzero entries. This was solved by BlockWiedemann. 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 latticesiever 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 
20050509, 17:03  #2 
Jul 2004
Potsdam, Germany
33F_{16} Posts 
They just looped over RSA640...
MANY CONGRATULATIONS TO F. Bahr, M. Boehm, J. Franke, T. Kleinjung! 
20050509, 18:58  #3 
Mar 2004
Belgium
34F_{16} Posts 
Yep congrats!!
Over wich RSA challenge number we are talking about? Or is this not correct??? Last fiddled with by ValerieVonck on 20050509 at 18:58 
20050509, 19:24  #4  
Jul 2004
Potsdam, Germany
3×277 Posts 
Good question...
The challenge website only states RSA640 (193 digits) and RSA704 (212 digits). One possibility is that RSA200 belongs to the "old" challenge: Quote:


20050509, 19:59  #5  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
11658_{10} Posts 
Quote:
Paul 

20050509, 20:06  #6 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
Very impressive. Any idea why they didn't do RSA640 first? Perhaps they expected that someone else (i.e. Kida) might factor that one before they could?
Alex 
20050509, 20:41  #7 
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 easytoremember number. The only thing that would be interesting left out of the summary was details of polynomial selection.
Sam 
20050509, 21:27  #8 
Apr 2004
Copenhagen, Denmark
2^{2}·29 Posts 
Full list of RSA numbers

20050510, 07:39  #9  
Bamboozled!
"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across
2×3×29×67 Posts 
Quote:
Distributing the money for rsa576 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 

20050510, 10:12  #10 
"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 
20050510, 12:53  #11 
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 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
RSA210 factored  ryanp  Factoring  6  20131126 09:33 
Factored vs. Completely factored  aketilander  Factoring  4  20120808 18:09 
F22 factored!  unconnected  Factoring  31  20100626 04:07 
F33 is factored !!  Raman  Factoring  4  20100401 13:57 
RSA100 factored!  ewmayer  Math  5  20030514 15:08 