mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2005-05-09, 16:39   #1
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

101010000111002 Posts
Exclamation 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
xilman is offline   Reply With Quote
Old 2005-05-09, 17:03   #2
Mystwalker
 
Mystwalker's Avatar
 
Jul 2004
Potsdam, Germany

11001111112 Posts
Default

They just looped over RSA-640...

MANY CONGRATULATIONS TO F. Bahr, M. Boehm, J. Franke, T. Kleinjung!
Mystwalker is offline   Reply With Quote
Old 2005-05-09, 18:58   #3
ValerieVonck
 
ValerieVonck's Avatar
 
Mar 2004
Belgium

292 Posts
Default

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
ValerieVonck is offline   Reply With Quote
Old 2005-05-09, 19:24   #4
Mystwalker
 
Mystwalker's Avatar
 
Jul 2004
Potsdam, Germany

3×277 Posts
Default

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.
Mystwalker is offline   Reply With Quote
Old 2005-05-09, 19:59   #5
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2A1C16 Posts
Default

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
xilman is offline   Reply With Quote
Old 2005-05-09, 20:06   #6
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

46438 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2005-05-09, 20:41   #7
trilliwig
 
trilliwig's Avatar
 
Oct 2004
tropical Massachusetts

3×23 Posts
Default

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
trilliwig is offline   Reply With Quote
Old 2005-05-09, 21:27   #8
JHansen
 
JHansen's Avatar
 
Apr 2004
Copenhagen, Denmark

22×29 Posts
Default Full list of RSA numbers

Here is the full list of the RSA Challenge numbers: RSA Number List

--
Cheers,
Jes
JHansen is offline   Reply With Quote
Old 2005-05-10, 07:39   #9
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

22×5×72×11 Posts
Default

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
xilman is offline   Reply With Quote
Old 2005-05-10, 10:12   #10
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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
akruppa is offline   Reply With Quote
Old 2005-05-10, 12:53   #11
BotXXX
 
BotXXX's Avatar
 
Aug 2003
Europe

2·97 Posts
Default

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
BotXXX is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
RSA-210 factored ryanp Factoring 6 2013-11-26 09:33
Factored vs. Completely factored aketilander Factoring 4 2012-08-08 18:09
F22 factored! unconnected Factoring 31 2010-06-26 04:07
F33 is factored !! Raman Factoring 4 2010-04-01 13:57
RSA-100 factored! 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.