mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

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

278 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

2·3·163 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

26·181 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

100111000001102 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

278 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

628 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

22×5×37 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

23·311 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 13:09.


Wed Dec 7 13:09:28 UTC 2022 up 111 days, 10:38, 0 users, load averages: 0.72, 0.78, 0.87

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

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”