mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2010-04-17, 14:34   #1
Eulero
 
Apr 2010

58 Posts
Default 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.
Eulero is offline   Reply With Quote
Old 2010-04-17, 18:36   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

33·131 Posts
Default

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 :)
jasonp is offline   Reply With Quote
Old 2010-04-17, 18:42   #3
Eulero
 
Apr 2010

5 Posts
Default

Which kind of tools can be used? Are there professional tools?
Eulero is offline   Reply With Quote
Old 2010-04-17, 19:54   #4
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

2·17·73 Posts
Default

Quote:
Originally Posted by jasonp View Post
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
Andi47 is offline   Reply With Quote
Old 2010-04-17, 20:01   #5
Eulero
 
Apr 2010

5 Posts
Default

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
Eulero is offline   Reply With Quote
Old 2010-04-17, 23:58   #6
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

67218 Posts
Default

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.
jasonp is offline   Reply With Quote
Old 2010-04-18, 07:39   #7
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2·5,323 Posts
Default

Quote:
Originally Posted by Eulero View Post
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
xilman is offline   Reply With Quote
Old 2010-04-18, 07:41   #8
Eulero
 
Apr 2010

5 Posts
Default

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
Eulero is offline   Reply With Quote
Old 2010-04-18, 08:35   #9
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

299616 Posts
Default

Quote:
Originally Posted by Eulero View Post
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
xilman is offline   Reply With Quote
Old 2010-04-18, 08:38   #10
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2×5,323 Posts
Default

Quote:
Originally Posted by Eulero View Post
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
xilman is offline   Reply With Quote
Old 2010-04-18, 09:10   #11
Eulero
 
Apr 2010

510 Posts
Default

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.
Eulero is offline   Reply With Quote
Reply

Thread Tools


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

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.