RSA-200 factored

xilman · 2005-05-09, 16:39

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

Mystwalker · 2005-05-09, 17:03

They just looped over RSA-640...

MANY CONGRATULATIONS TO F. Bahr, M. Boehm, J. Franke, T. Kleinjung!

ValerieVonck · 2005-05-09, 18:58

Yep congrats!!

Over wich RSA challenge number

we are talking about?
Or is this not correct???

Mystwalker · 2005-05-09, 19:24

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.

xilman · 2005-05-09, 19:59

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

akruppa · 2005-05-09, 20:06

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

trilliwig · 2005-05-09, 20:41

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

JHansen · 2005-05-09, 21:27

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

--
Cheers,
Jes

xilman · 2005-05-10, 07:39

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

akruppa · 2005-05-10, 10:12

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

BotXXX · 2005-05-10, 12:53

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

2005-05-09, 18:58	#3
ValerieVonck Mar 2004 Belgium 34F₁₆ 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, 21:27	#8
JHansen Apr 2004 Copenhagen, Denmark 2²·29 Posts	Full list of RSA numbers Here is the full list of the RSA Challenge numbers: RSA Number List -- Cheers, Jes

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

2005-05-09, 17:03	#2
Mystwalker Jul 2004 Potsdam, Germany 33F₁₆ Posts	They just looped over RSA-640... MANY CONGRATULATIONS TO F. Bahr, M. Boehm, J. Franke, T. Kleinjung!

2005-05-09, 20:06	#6
akruppa "Nancy" Aug 2002 Alexandria 2,467 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-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