mersenneforum.org RSA-640 factored
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2005-11-07, 17:34   #1
xilman
Bamboozled!

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

2·61·83 Posts
RSA-640 factored

Apologies if this has been seen elsewhere. I've only just returned from a 4-day trip to find the mail below in my inbox.

Another impressive result from Franke et al.

Quote:
 Originally Posted by Jens Franke et al. We have factored RSA640 by GNFS. The factors are 16347336458092538484431338838650908598417836700330\ 92312181110852389333100104508151212118167511579 and 19008712816648221131268515739354139754718967899685\ 15493666638539088027103802104498957191261465571 We did lattice sieving for most special q between 28e7 and 77e7 using factor base bounds of 28e7 on the algebraic side and 15e7 on the rational side. The bounds for large primes were 2^34. This produced 166e7 relations. After removing duplicates 143e7 relations remained. A filter job produced a matrix with 36e6 rows and columns, having 74e8 non-zero entries. This was solved by Block-Lanczos. Sieving has been done on 80 2.2 GHz Opteron CPUs and took 3 months. The matrix step was performed on a cluster of 80 2.2 GHz Opterons connected via a Gigabit network and took about 1.5 months. Calendar time for the factorization (without polynomial selection) was 5 months. More details will be given later. F. Bahr, M. Boehm, J. Franke, T. Kleinjung

Paul

 2005-11-07, 19:52 #2 sean     Aug 2004 New Zealand 3·73 Posts Yep, congratulation to Franke et al. again! I believe the all time top 10 for GNFS is now: Code: RSA-200 2005 2799 C200=P100*P100 GNFS Bahr/Franke/Kleinjung/et al. RSA640 2005 3107 C193=P98*P98 GNFS Bahr/Franke/Kleinjung/et al. 11^281+1 2005 1009 C176=P87*P89 GNFS Aoki/Kida/Shimoyama/Ueda RSA-576 2003 1881 C174=P87*P87 GNFS Bahr/Franke/Kleinjung/Montgomery/te Riele/Leclair/Leyland/Wackerbarth 2^1826+1 2003 9758 C164=P68*P97 GNFS Aoki/Kida/Shimoyama/Sonoda/Ueda RSA-160 2003 2152 C160=P80*P80 GNFS Bahr/Franke/Kleinjung/Lochter/Bohm 2^953+1 2002 3950 C158=P73*P86 GNFS Bahr/Franke/Kleinjung RSA-155 1999 1094 C155=P78*P78 GNFS te Riele/CWI et al. Code Book 2000 1074 C155=P78*P78 GNFS Almgren/Andersson/Granlund/Ivansson/Ulfberg HP49(95) 2003 2651 C153=P68*P85 GNFS Kruppa/Leyland
 2005-11-07, 20:03 #3 Citrix     Jun 2003 30478 Posts WHat program do you use for GNFS? Citrix
2005-11-07, 20:10   #4
sean

Aug 2004
New Zealand

3×73 Posts

Quote:
 Originally Posted by Citrix WHat program do you use for GNFS? Citrix
Check out the Links to programs thread.

For these record breakers, Franke et al. almost certainly had to make several modifications to their own code. You need to start with something smaller than these record breakers, say in the range C110-C135. The GGNFS implementation is probably a good place to start (although I haven't used it myself).

2005-11-07, 20:20   #5
Citrix

Jun 2003

32·52·7 Posts

Quote:
 Originally Posted by sean Check out the Links to programs thread. For these record breakers, Franke et al. almost certainly had to make several modifications to their own code. You need to start with something smaller than these record breakers, say in the range C110-C135. The GGNFS implementation is probably a good place to start (although I haven't used it myself).

Are there any binaries for windows?

Citrix

2005-11-07, 20:24   #6
rogue

"Mark"
Apr 2003
Between here and the

5,953 Posts

Quote:
 Originally Posted by sean For these record breakers, Franke et al. almost certainly had to make several modifications to their own code. You need to start with something smaller than these record breakers, say in the range C110-C135. The GGNFS implementation is probably a good place to start (although I haven't used it myself).
GGNFS is limited to under 130 digits for a gnfs factorization. I've been playing around with a few between 120 and 125 digits, but more work needs to be done to determine the optimal parameters.

 2005-11-07, 20:42 #7 BotXXX     Aug 2003 Europe 193 Posts Congrats to F. Bahr, M. Boehm, J. Franke, T. Kleinjung. But running a cluster of 80 2.2 GHz Opterons can be a bit of energy consumption. But they also used the cluster in the solving of the matrix? Will this mean that they made a good matrix solving piece of code that spreads good on clusters? I am curious about their code.
2005-11-07, 21:39   #8
R.D. Silverman

Nov 2003

26·113 Posts

Quote:
 Originally Posted by xilman Apologies if this has been seen elsewhere. I've only just returned from a 4-day trip to find the mail below in my inbox. Another impressive result from Franke et al. Paul
Notice that the Linear Algebra took half as much total CPU time as the
sieving......

 2005-11-08, 00:07 #9 pacionet     Oct 2005 Italy 3×113 Posts RSA 640 factored ? A distributed computing project tried to solve it (http://www.primegrid.com). now they must change work ...
2005-11-08, 03:56   #10
ColdFury

Aug 2002

26·5 Posts

Quote:
 Originally Posted by pacionet RSA 640 factored ? A distributed computing project tried to solve it (http://www.primegrid.com). now they must change work ...
Not like they had a chance anyways.

2005-11-08, 11:14   #11
xilman
Bamboozled!

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

2×61×83 Posts

Quote:
 Originally Posted by R.D. Silverman Notice that the Linear Algebra took half as much total CPU time as the sieving......
Under-sieving, IMO.

I'm sure they could have got the LA time down substantially if they had spent more sieving. However, they would have had an even harder time with the data handling and filtering.

Asymptotically the sieving and LA times should be equal. I don't believe that RSA-640 is anywhere near big enough for that rule to be particularly useful.

Paul

 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 15:53.

Wed Oct 28 15:53:18 UTC 2020 up 48 days, 13:04, 3 users, load averages: 1.70, 1.57, 1.68