My plan for RSA factoring distributed computing

[stathmk]

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.

[bsquared]

Originally Posted by stathmk

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.

[frmky]

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.

[stathmk]

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.

[fivemack]

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

[bsquared]

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.

[stathmk]

Originally Posted by fivemack

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

Thank you. Now I'll first try 109!+1 a bit before going on to the RSA numbers.

[alpertron]

Originally Posted by stathmk

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.

[stathmk]

Hi Dario.

Originally Posted by alpertron

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.

[10metreh]

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.

[stathmk]

Originally Posted by 10metreh

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.