mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Open Projects

Reply
 
Thread Tools
Old 2009-03-16, 00:25   #1
stathmk
 
stathmk's Avatar
 
Mar 2009
Indiana, United Stat

24·3 Posts
Lightbulb My plan for RSA factoring distributed computing

Hi, guys. I’m new here.

Let me show you some of my background that I am serious. I have a prime curio at http://primes.utm.edu/curios/page.php?number_id=5581 . I have discovered many primes using Alpertron's web site, Proth, NewPGen, and Primeform. There also are the primes that I’ve discovered with over 10,000 digits:
10816*10^20354+1 (20,359 digits)
10816*10^14192+1 (14,197 digits)
(2^19780)^2+(2^19780)+41 (11,909 digits)
10816*10^11066+1 (11,071 digits)
(10^5059)^2+(10^5059)+41 (10,119 digits)
…and two of them are at http://www.primenumbers.net/prptop/prptop.php if you do the form search for Matt Stath

None of my primes are at The Prime Pages’ top 5000.

I also have a different prime record. Go to http://www.alpertron.com.ar/ECM.htm and part of the way down the screen click on “See Factorization Records.” My 49-digit factor is first place for now. It took over six months to factor using Dario Alejandro Alpern’s ECM Applet. For now, I’m trying to break my record again.

I saw the ECMNET Project at http://www.loria.fr/~zimmerma/records/ecmnet.html and the first thing that it reminded me of was Alpertron’s web site.

I'm sure you’ve heard of the RSA factorization challenge:
http://en.wikipedia.org/wiki/RSA_Factoring_Challenge

There are different programs that I could use to factor the RSA-170 number from the Wikipedia page. Which GNFS program do you recommend to me? I’ve used Alpertron, PrimeForm, NewPGen, and Proth, but never a SNFS, MPQS, GNFS or ECPP program yet.

I want to have a Factoring Project and have it listed here: http://mersenneforum.org/showthread.php?t=9611

You’ve heard of different terminology for distributed computer systems like SETI, programs to research folding proteins, and others. They are called number crunchers, data miners, render farms, synergy programs, and other names. I want to set up a dot com site with range charts where I have people sign up by email for ranges using http://www.alpertron.com.ar/ECM.htm to first factor RSA-170, and then on to the next RSA numbers with SNFS, MPQS, GNFS, ECPP, or whatever is the most efficient. I want to put this on my resume, make it mentioned on Math web sites, and recommend it to some friends to get it promoted. The dot com site probably will have RSA in the URL.

Please post links for other factorization program records like http://www.alpertron.com.ar/ECMREC.HTM and http://www.loria.fr/~zimmerma/records/ecmnet.html if you know of any.

Please tell me your knowledge of which program (SNFS, MPQS, GNFS or ECPP) would be the most efficient for factoring the unsolved RSA semiprimes, which have 170 to 617 digits.

I’m about ready to contact RSA with some questions.

Thank you.
stathmk is offline   Reply With Quote
Old 2009-03-16, 02:55   #2
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

DFA16 Posts
Default

Quote:
Originally Posted by stathmk View Post


There are different programs that I could use to factor the RSA-170 number from the Wikipedia page. Which GNFS program do you recommend to me? I’ve used Alpertron, PrimeForm, NewPGen, and Proth, but never a SNFS, MPQS, GNFS or ECPP program yet.
Leaders of projects are generally knowledgable about what they are leading... you have some homework to do.

For starters, for RSA type numbers, GNFS is your only option. The best publicly available implementation is called GGNFS (google). Threads on this forum and the yahoo group has info to get you going on learning how to use it.

Best of luck. My CPUs will be busy elsewhere.
bsquared is offline   Reply With Quote
Old 2009-03-16, 05:05   #3
frmky
 
frmky's Avatar
 
Jul 2003
So Cal

22·547 Posts
Default

RSA-170 is a bit easier than 109!+1. Take a look at the 109!+1 poly search and sieving threads to get an idea of the amount of work involved.
frmky is offline   Reply With Quote
Old 2009-03-16, 16:37   #4
stathmk
 
stathmk's Avatar
 
Mar 2009
Indiana, United Stat

24×3 Posts
Question Re: RSA semiprimes, 109!+1

Thanks, guys.

Yes, I already knew that I have some homework to do.

I did an internet search for GGNFS and it seems to be helpful.

Frmky, please link me to the 109!+1 pages that you're talking about. I did an internet search for 109!+1 polynomial search and it wasn't helpful. It returned results like page 109, chapter 109, or volume 109.
stathmk is offline   Reply With Quote
Old 2009-03-16, 16:43   #5
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

192616 Posts
Default

http://www.mersenneforum.org/showthread.php?t=11454
fivemack is offline   Reply With Quote
Old 2009-03-16, 16:46   #6
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

1101111110102 Posts
Default

And for the sieving...

http://www.mersenneforum.org/showthread.php?t=11529

I see that the sieving so far has consumed about 944 CPU days, and isn't done yet.
bsquared is offline   Reply With Quote
Old 2009-03-16, 16:58   #7
stathmk
 
stathmk's Avatar
 
Mar 2009
Indiana, United Stat

3016 Posts
Thumbs up Re: 109!+1

Quote:
Originally Posted by fivemack View Post
Thank you. Now I'll first try 109!+1 a bit before going on to the RSA numbers.
stathmk is offline   Reply With Quote
Old 2009-03-16, 17:14   #8
alpertron
 
alpertron's Avatar
 
Aug 2002
Buenos Aires, Argentina

22·3·5·23 Posts
Default

Quote:
Originally Posted by stathmk View Post
I also have a different prime record. Go to http://www.alpertron.com.ar/ECM.htm and part of the way down the screen click on “See Factorization Records.” My 49-digit factor is first place for now. It took over six months to factor using Dario Alejandro Alpern’s ECM Applet. For now, I’m trying to break my record again.
With the new version of my factoring applet it should take less than 2 days to factor RSA-99 using SIQS. I haven't ran that number but you can do it easily: after the factorization starts, type the number zero on the lower-left input box and then press New Curve button.

Of course applets are not as fast as native code, so msieve can factor the same number in about 8 hours (the exact number depends on the processor you are using).

I appreciate you post the output from the applet after the factorization finishes.

Last fiddled with by alpertron on 2009-03-16 at 17:15
alpertron is offline   Reply With Quote
Old 2009-03-16, 18:06   #9
stathmk
 
stathmk's Avatar
 
Mar 2009
Indiana, United Stat

24×3 Posts
Thumbs up RSA-99

Hi Dario.
Quote:
Originally Posted by alpertron View Post
With the new version of my factoring applet it should take less than 2 days to factor RSA-99 using SIQS. I haven't ran that number but you can do it easily: after the factorization starts, type the number zero on the lower-left input box and then press New Curve button. ...
Yes, I will try that before too many days. According to both our records, I finished factoring it by curves on July 10, 2008. You've been updating your SIQS code about every week since January 1st, 2009, so it's very different since July.
stathmk is offline   Reply With Quote
Old 2009-03-16, 18:25   #10
10metreh
 
10metreh's Avatar
 
Nov 2008

2·33·43 Posts
Default

I'd try doing something like RSA-100 with GNFS before you get to the big jobs like RSA-170. And ECM would take millennia. I mean millennia. Well CPU-millennia, anyway, for RSA-170, that is. And Dario's applet is only really competitive with GMP-ECM for the 25-digit level and below.

There are several people who go around trying to factor huge numbers with ECM or even (fanfare) trial division. Some are told off and continue. I hope you are not one of them.
10metreh is offline   Reply With Quote
Old 2009-03-16, 20:49   #11
stathmk
 
stathmk's Avatar
 
Mar 2009
Indiana, United Stat

24·3 Posts
Default

Quote:
Originally Posted by 10metreh View Post
I'd try doing something like RSA-100 with GNFS before you get to the big jobs like RSA-170. And ECM would take millennia. I mean millennia. Well CPU-millennia, anyway, for RSA-170, that is. And Dario's applet is only really competitive with GMP-ECM for the 25-digit level and below.

There are several people who go around trying to factor huge numbers with ECM or even (fanfare) trial division. Some are told off and continue. I hope you are not one of them.
I'm factoring a 119-digit number using Alpertron's web site. I'll eventually have people sign up for ranges for the 119-digit number. I'm still studying ECMNET and GGNFS. Now, instead of using Alpertron's web site to factor RSA-170, I'll have to use ECMNET http://www.loria.fr/~zimmerma/records/ecmnet.html or GGFNS. It will be GGFNS for everything above RSA-170.
stathmk is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Etiquettes of Distributed Computing a1call Miscellaneous Math 8 2018-05-21 16:25
Massively distributed computing and factoring... flouran Math 2 2009-11-21 05:30
Distributed Computing Survey garo Lounge 11 2004-09-01 03:31
The difference between P2P and distributed computing and grid computing GP2 Lounge 2 2003-12-03 14:13
P-1 factoring as distributed computing jocelynl Math 2 2002-11-23 00:27

All times are UTC. The time now is 16:43.


Sun Oct 17 16:43:33 UTC 2021 up 86 days, 11:12, 1 user, load averages: 1.65, 1.37, 1.18

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.