mersenneforum.org RSA-768 factoring algorythm
 Register FAQ Search Today's Posts Mark Forums Read

 2010-04-17, 14:34 #1 Eulero   Apr 2010 58 Posts RSA-768 factoring algorythm I read the article about RSA-768 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.
 2010-04-17, 18:36 #2 jasonp Tribal Bullet     Oct 2004 33·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 :)
 2010-04-17, 18:42 #3 Eulero   Apr 2010 5 Posts Which kind of tools can be used? Are there professional tools?
2010-04-17, 19:54   #4
Andi47

Oct 2004
Austria

2·17·73 Posts

Quote:
 Originally Posted by jasonp Msieve is not limited to 100 digits, and has helped factor much larger numbers than that.
To be a bit more precise:

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 120-digit-number with MPQS, but it's waste of time.)

For (general) numbers above ~90-100 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 2010-04-17 at 20:00

 2010-04-17, 20:01 #5 Eulero   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 2010-04-17 at 20:03
 2010-04-17, 23:58 #6 jasonp Tribal Bullet     Oct 2004 67218 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 industrial-strength NFS polynomial selection.
2010-04-18, 07:39   #7
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

2·5,323 Posts

Quote:
 Originally Posted by Eulero I read the article about RSA-768 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.
Yes it is possible. That's the answer to both questions, by the way.

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 RSA-768. My contribution was entirely from Linux boxen.

Paul

Paul

2010-04-18, 07:41   #8
Eulero

Apr 2010

5 Posts

Factoring the RSA-768 as well the RSA-1024 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 RSA-768 factoring date. Many thanks for the informations you provided.

Quote:
 My contribution was entirely from Linux boxen
Kind Paul, My compliments for having given a contribution to such an hard work.

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 2010-04-18 at 07:52

2010-04-18, 08:35   #9
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

299616 Posts

Quote:
 Originally Posted by Eulero I bet the most part of implementation codes are written in C++, the code should be not so different between linux and windows.
C, actually.

At least 99% of the code should be completely operating system independent.

Paul

2010-04-18, 08:38   #10
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

2×5,323 Posts

Quote:
 Originally Posted by Eulero 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.
As far as I am aware, CUDA performance is essentially the same under all supported operating systems. I've not noticed any significant difference under Win7, RedHat EL5 and MacOS Snow Leopard.

It's certainly possible to share work between GPU and CPU programs. That's how most non-trivial CUDA programs work. The GPU does the arithmetic-intensive work and the CPU does everything else.

Paul

 2010-04-18, 09:10 #11 Eulero   Apr 2010 510 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.

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

Mon Apr 19 08:35:59 UTC 2021 up 11 days, 3:16, 0 users, load averages: 1.15, 1.39, 1.46

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.