mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

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

2·61·83 Posts
Exclamation 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
xilman is offline   Reply With Quote
Old 2005-11-07, 19:52   #2
sean
 
sean's Avatar
 
Aug 2004
New Zealand

3·73 Posts
Default

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
sean is offline   Reply With Quote
Old 2005-11-07, 20:03   #3
Citrix
 
Citrix's Avatar
 
Jun 2003

30478 Posts
Default

WHat program do you use for GNFS?

Citrix
Citrix is offline   Reply With Quote
Old 2005-11-07, 20:10   #4
sean
 
sean's Avatar
 
Aug 2004
New Zealand

3×73 Posts
Default

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).
sean is offline   Reply With Quote
Old 2005-11-07, 20:20   #5
Citrix
 
Citrix's Avatar
 
Jun 2003

32·52·7 Posts
Default

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
Citrix is offline   Reply With Quote
Old 2005-11-07, 20:24   #6
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

5,953 Posts
Default

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.
rogue is offline   Reply With Quote
Old 2005-11-07, 20:42   #7
BotXXX
 
BotXXX's Avatar
 
Aug 2003
Europe

193 Posts
Default

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.
BotXXX is offline   Reply With Quote
Old 2005-11-07, 21:39   #8
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26·113 Posts
Default

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......
R.D. Silverman is offline   Reply With Quote
Old 2005-11-08, 00:07   #9
pacionet
 
pacionet's Avatar
 
Oct 2005
Italy

3×113 Posts
Default

RSA 640 factored ?




A distributed computing project tried to solve it (http://www.primegrid.com).
now they must change work ...
pacionet is offline   Reply With Quote
Old 2005-11-08, 03:56   #10
ColdFury
 
ColdFury's Avatar
 
Aug 2002

26·5 Posts
Default

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

2×61×83 Posts
Default

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
xilman 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 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.