mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2012-07-02, 12:25   #1
bai
 
May 2011

1716 Posts
Default Factorization of RSA704

Hi all,

RSA704 is factored. A report describing the details of the factorization effort can be found on http://maths.anu.edu.au/~bai

Best regards,
Shi
bai is offline   Reply With Quote
Old 2012-07-02, 17:21   #2
debrouxl
 
debrouxl's Avatar
 
Sep 2009

977 Posts
Default

Good job
debrouxl is offline   Reply With Quote
Old 2012-07-02, 17:23   #3
otchij
 
Nov 2010

32 Posts
Default

My congratulations with successful silver grade factorization!

It is nice to see that CADO-NFS is mature enough to handle such dimension.

Just small questions about your achievement:

1) 2^33 used as large prime bound on both sides. Thus special q range should be from 500M to 8589M. In report we see 10000M as an upper boundary. Is it possible to point the largest special q value in your sieving?

2) The second stage (lingen) in block Wiedemann algorithm was taking 10 days. What version of lingen are you using? Single-thread, multi-thread or something else?

Best Regards
otchij is offline   Reply With Quote
Old 2012-07-02, 17:33   #4
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2·3·17·103 Posts
Default

Quote:
Originally Posted by bai View Post
Hi all,

RSA704 is factored. A report describing the details of the factorization effort can be found on http://maths.anu.edu.au/~bai

Best regards,
Shi
The other Paul has just mailed the usual suspects with this result.
Paul

Last fiddled with by xilman on 2012-07-02 at 19:43 Reason: Redaction made on request. It may be reversed.
xilman is offline   Reply With Quote
Old 2012-07-02, 19:22   #5
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2×11×421 Posts
Default

Stupendous job!
(degree 6, too - very good test)

What was the degree 5 best polynomial?
Batalov is offline   Reply With Quote
Old 2012-07-03, 06:54   #6
bai
 
May 2011

23 Posts
Default

Quote:
Originally Posted by otchij View Post
My congratulations with successful silver grade factorization!

It is nice to see that CADO-NFS is mature enough to handle such dimension.

Just small questions about your achievement:

1) 2^33 used as large prime bound on both sides. Thus special q range should be from 500M to 8589M. In report we see 10000M as an upper boundary. Is it possible to point the largest special q value in your sieving?

2) The second stage (lingen) in block Wiedemann algorithm was taking 10 days. What version of lingen are you using? Single-thread, multi-thread or something else?

Best Regards
Thanks otchij. Paul mentioned that "Indeed some special-q were above the large prime bound. The largest special-q was 9999999929 (which gave 3 relations in total). This is not really a problem since we can merge all k relations with a given special-q, to obtain k-1 relation-sets without this special-q. Currently CADO-NFS only implements a single-thread version of lingen. It is planned to completely rewrite this program."
bai is offline   Reply With Quote
Old 2012-07-03, 07:05   #7
bai
 
May 2011

23 Posts
Default

Quote:
Originally Posted by Batalov View Post
Stupendous job!
(degree 6, too - very good test)

What was the degree 5 best polynomial?
Thanks Batalov. As far as I can locate, the best deg 5 poly is,

Quote:
Y1: 49758016715758193
Y0: -62594076250212057850135759159429623544504
c5: 77052360
c4: -842263139899117196
c3: 3877551127632265865220186773
c2: 1349801344279038732547104688214106165
c1: -1381013605456477529347256999964508765576480869
c0: -112375960656174315827082110714419649578392608747527665
# lognorm: 71.08, alpha: -8.60 (proj: -1.96), E: 62.48,
# Murphy's E=4.04e-16
which is about half of the E of the deg 6 one (assuming we can compare polynomials of different degree directly.) It was found by a previous version of polyselect2.c inside polyselect/ folder. As then we mostly focused on deg 6 polynomials, and continued until we found something matching/above the targeted Murphy E (e.g. the projected E's on http://maths.anu.edu.au/~bai/proj_E/).

Last fiddled with by bai on 2012-07-03 at 07:12 Reason: typo
bai is offline   Reply With Quote
Old 2012-07-04, 10:14   #8
poily
 
Nov 2010

2·52 Posts
Default

Congrats, nice job! Not so much feasible unfactored RSA numbers left.
poily is offline   Reply With Quote
Old 2012-07-04, 16:47   #9
Stargate38
 
Stargate38's Avatar
 
"Daniel Jackson"
May 2011
14285714285714285714

72×13 Posts
Default

Yes. Lets hope they find a way to factor RSA-1024. I've been waiting a long time for that.
Stargate38 is offline   Reply With Quote
Old 2012-07-04, 18:10   #10
ixfd64
Bemusing Prompter
 
ixfd64's Avatar
 
"Danny"
Dec 2002
California

2,351 Posts
Default

Quote:
Originally Posted by poily View Post
Congrats, nice job! Not so much feasible unfactored RSA numbers left.
But still a lot.
ixfd64 is offline   Reply With Quote
Old 2012-07-04, 18:38   #11
Dubslow
Basketry That Evening!
 
Dubslow's Avatar
 
"Bunslow the Bold"
Jun 2011
40<A<43 -89<O<-88

3×29×83 Posts
Default

Quote:
Originally Posted by ixfd64 View Post
The smallest is RSA-210, and I'm pretty sure NFS@Home could sieve that, much like B200. RSA-704 was 212 digits.

Last fiddled with by Dubslow on 2012-07-04 at 18:43
Dubslow is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factorization of RSA-180 Robert Holmes Factoring 19 2010-11-08 18:46
Factorization on 2^p +1 kurtulmehtap Math 25 2010-09-12 14:13
RSA704, ggnfs? (good polynoms?) Random_zh Factoring 8 2006-12-13 13:13
Factorization of 7,254+ dleclair NFSNET Discussion 1 2006-03-21 05:11
Factorization of 11,212+ Wacky NFSNET Discussion 1 2006-03-20 23:43

All times are UTC. The time now is 08:33.

Fri Jan 22 08:33:04 UTC 2021 up 50 days, 4:44, 0 users, load averages: 1.70, 1.54, 1.52

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.