20100417, 14:34  #1 
Apr 2010
5_{8} Posts 
RSA768 factoring algorythm
I read the article about RSA768 http://eprint.iacr.org/2010/006.pdf
I would like to know if it's possible to implement such an algorythm for windows taking advantage of newest Intel i480x CPUs and CUDA Geforce GTX 480; using the most recent powerful processors could it be possible to make a plynomial selction on one machine instead of a cluster? I saw msieve is limited to a 100 digits number, is it possible to extend it to larger numbers? Thanks. 
20100417, 18:36  #2 
Tribal Bullet
Oct 2004
3^{3}·131 Posts 
Msieve is not limited to 100 digits, and has helped factor much larger numbers than that.
Publicly available tools cannot do the postprocessing for a number the size of RSA768; give it a few years :) 
20100417, 18:42  #3 
Apr 2010
5 Posts 
Which kind of tools can be used? Are there professional tools?

20100417, 19:54  #4  
Oct 2004
Austria
2·17·73 Posts 
Quote:
Msieve's MPQS should not be used to factor numbers above 100 digits, as GNFS is faster for such numbers. (depending on the computer the size where GNFS becomes faster than MPQS is somewhere between 85 and 95 digits. BTW: It is POSSIBLE to factor a 120digitnumber with MPQS, but it's waste of time.) For (general) numbers above ~90100 digits (i.e. such ones which no special forms like a^b+/1) GNFS with the following procedure should be used: 1.) Polynomial search, using Msieve 2.) sieving, using GGNFS (GGNFS is much faster than msieve for NFS sieving) 3.) postprocessing (= matrix step and square root), using Msieve. Edit: This will work up to ~185 (or maybe 190) digits  absolutely no chance to do a 231 digit number (=RSA768) with these tools. Last fiddled with by Andi47 on 20100417 at 20:00 

20100417, 20:01  #5 
Apr 2010
5 Posts 
Many thanks, I made a mistake, the limit wasn't set to 100 digits.
Yes, I knew the steps could be made separately.The msieve limit is 200 digits, very close to 232 but not enough. Are there different professional tools? Not free of course. At least for the 1st step polynomial selection. Last fiddled with by Eulero on 20100417 at 20:03 
20100417, 23:58  #6 
Tribal Bullet
Oct 2004
6721_{8} Posts 
Use of the word 'professional' implies there are tools for sale that will break RSA keys. There are no such; who would buy them?
The tools that found the polynomial for RSA768 are probably part of the CWI NFS suite, and you could ask Herman te Riele for a license. The other major tool would be from Thorsten Kleinjung, whose pol5 code is in GGNFS and whose latest code is much better but not publicly available. You could ask him for a copy too. The above plus msieve are pretty much the only available choices for industrialstrength NFS polynomial selection. 
20100418, 07:39  #7  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2·5,323 Posts 
Quote:
Just because it is possible does not mean that it is easy. Neither does it mean that a single Windows box with a GPU will be faster than a cluster. I have no idea whether any Windows machines were used in factoring RSA768. My contribution was entirely from Linux boxen. Paul Paul 

20100418, 07:41  #8  
Apr 2010
5 Posts 
Factoring the RSA768 as well the RSA1024 is useless to me, my real aim is to see if the newest CPUs and GPUs can make a work which could have only been possible with computer clusters up to the RSA768 factoring date. Many thanks for the informations you provided.
Quote:
I bet the most part of implementation codes are written in C++, the code should be not so different between linux and windows. The problem for me is I used Ubuntu (for example) some times, but I'm more familiar with writing programs under windows. I also don't know if Linux drivers for Nvidia CUDA GPUs are really optimized as windows', but I'm not sure about this, just wondering. I guess it's not possible to share work between multicore CPUs and CUDA GPUs, I heard if you write for CUDA , multicore CPUs are not involved and vice versa. Last fiddled with by Eulero on 20100418 at 07:52 

20100418, 08:35  #9 
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2996_{16} Posts 

20100418, 08:38  #10  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2×5,323 Posts 
Quote:
It's certainly possible to share work between GPU and CPU programs. That's how most nontrivial CUDA programs work. The GPU does the arithmeticintensive work and the CPU does everything else. Paul 

20100418, 09:10  #11 
Apr 2010
5_{10} Posts 
Mnay thanks for this news, very good. I can have access to huge Intel and Nvidia resources for testing purposes, so I could have the chance to test if at least polynomial slection could be significantly speed up by latest technologies.
According to the suggestion of the kind jasonp it would be good to get in touch with Herman te Riele who has already developed an algrythm handling numbers larger than 200 digits, and see how to implement (or ask for a license). The point is to make the same work they did on several machines using a significantly lesser number of machines by taking advantage of latest technologies. Since you already gave a contribution, do you know how hard is to make a prog handling more than 200 digits for polynomial selection? Many thanks for all the informations you gave me. 