mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Open Projects (https://www.mersenneforum.org/forumdisplay.php?f=80)
-   -   My plan for RSA factoring distributed computing (https://www.mersenneforum.org/showthread.php?t=11601)

 stathmk 2009-03-16 00:25

My plan for RSA factoring distributed computing

[FONT=Times New Roman][SIZE=3]Hi, guys. I’m new here.[/SIZE][/FONT]

[FONT=Times New Roman][SIZE=3]Let me show you some of my background that I am serious. I have a prime curio at [/SIZE][/FONT][URL="http://primes.utm.edu/curios/page.php?number_id=5581"][FONT=Times New Roman][SIZE=3][COLOR=#800080]http://primes.utm.edu/curios/page.php?number_id=5581[/COLOR][/SIZE][/FONT][/URL][SIZE=3][FONT=Times New Roman] . 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:[/FONT][/SIZE]
[SIZE=3][FONT=Times New Roman]10816*10^20354+1 (20,359 digits)[/FONT][/SIZE]
[SIZE=3][FONT=Times New Roman]10816*10^14192+1 (14,197 digits)[/FONT][/SIZE]
[SIZE=3][FONT=Times New Roman](2^19780)^2+(2^19780)+41 (11,909 digits) [/FONT][/SIZE]
[SIZE=3][FONT=Times New Roman]10816*10^11066+1 (11,071 digits)[/FONT][/SIZE]
[SIZE=3][FONT=Times New Roman](10^5059)^2+(10^5059)+41 (10,119 digits)[/FONT][/SIZE]
[FONT=Times New Roman][SIZE=3]…and two of them are at [/SIZE][/FONT][URL="http://www.primenumbers.net/prptop/prptop.php"][FONT=Times New Roman][SIZE=3][COLOR=#800080]http://www.primenumbers.net/prptop/prptop.php[/COLOR][/SIZE][/FONT][/URL][SIZE=3][FONT=Times New Roman] if you do the form search for Matt Stath [/FONT][/SIZE]

[FONT=Times New Roman][SIZE=3]None of my primes are at The Prime Pages’ top 5000. [/SIZE][/FONT]

[FONT=Times New Roman][SIZE=3]I also have a different prime record. Go to [/SIZE][/FONT][URL="http://www.alpertron.com.ar/ECM.htm"][FONT=Times New Roman][SIZE=3][COLOR=#800080]http://www.alpertron.com.ar/ECM.htm[/COLOR][/SIZE][/FONT][/URL][SIZE=3][FONT=Times New Roman] 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.[/FONT][/SIZE]

[FONT=Times New Roman][SIZE=3]I saw the ECMNET Project at [/SIZE][/FONT][URL="http://www.loria.fr/~zimmerma/records/ecmnet.html"][FONT=Times New Roman][SIZE=3][COLOR=#0000ff]http://www.loria.fr/~zimmerma/records/ecmnet.html[/COLOR][/SIZE][/FONT][/URL][SIZE=3][FONT=Times New Roman] and the first thing that it reminded me of was Alpertron’s web site.[/FONT][/SIZE]

[SIZE=3][FONT=Times New Roman]I'm sure you’ve heard of the RSA factorization challenge:[/FONT][/SIZE]
[URL="http://en.wikipedia.org/wiki/RSA_Factoring_Challenge"][FONT=Times New Roman][SIZE=3][COLOR=#800080]http://en.wikipedia.org/wiki/RSA_Factoring_Challenge[/COLOR][/SIZE][/FONT][/URL]

[SIZE=3][FONT=Times New Roman]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.[/FONT][/SIZE]

[FONT=Times New Roman][SIZE=3]I want to have a Factoring Project and have it listed here: [/SIZE][/FONT][URL="http://mersenneforum.org/showthread.php?t=9611"][FONT=Times New Roman][SIZE=3][COLOR=#0000ff]http://mersenneforum.org/showthread.php?t=9611[/COLOR][/SIZE][/FONT][/URL]

[FONT=Times New Roman][SIZE=3]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 [/SIZE][/FONT][URL="http://www.alpertron.com.ar/ECM.htm"][FONT=Times New Roman][SIZE=3][COLOR=#800080]http://www.alpertron.com.ar/ECM.htm[/COLOR][/SIZE][/FONT][/URL][SIZE=3][FONT=Times New Roman] 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.[/FONT][/SIZE]

[FONT=Times New Roman][SIZE=3]Please post links for other factorization program records like [/SIZE][/FONT][URL="http://www.alpertron.com.ar/ECMREC.HTM"][FONT=Times New Roman][SIZE=3][COLOR=#800080]http://www.alpertron.com.ar/ECMREC.HTM[/COLOR][/SIZE][/FONT][/URL][FONT=Times New Roman][SIZE=3] and [/SIZE][/FONT][URL="http://www.loria.fr/~zimmerma/records/ecmnet.html"][FONT=Times New Roman][SIZE=3][COLOR=#0000ff]http://www.loria.fr/~zimmerma/records/ecmnet.html[/COLOR][/SIZE][/FONT][/URL][FONT=Times New Roman][SIZE=3] if you know of any.[/SIZE][/FONT]

[FONT=Times New Roman][SIZE=3]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.[/SIZE][/FONT]

[SIZE=3][FONT=Times New Roman]Thank you.[/FONT][/SIZE]

 bsquared 2009-03-16 02:55

[quote=stathmk;165501]

[SIZE=3][FONT=Times New Roman]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.[/FONT][/SIZE]
[FONT=Times New Roman][SIZE=3][/SIZE][/FONT]
[/quote]

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 2009-03-16 05:05

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 2009-03-16 16:37

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 [B]109!+1 polynomial search [/B]and it wasn't helpful. It returned results like page 109, chapter 109, or volume 109.

 fivemack 2009-03-16 16:43

 bsquared 2009-03-16 16:46

And for the sieving...

I see that the sieving so far has consumed about 944 CPU days, and isn't done yet.
[/SIZE]

 stathmk 2009-03-16 16:58

Re: 109!+1

[quote=fivemack;165590][URL]http://www.mersenneforum.org/showthread.php?t=11454[/URL][/quote]Thank you. Now I'll first try 109!+1 a bit before going on to the RSA numbers.

 alpertron 2009-03-16 17:14

[QUOTE=stathmk;165501]
[FONT=Times New Roman][SIZE=3]I also have a different prime record. Go to [/SIZE][/FONT][URL="http://www.alpertron.com.ar/ECM.htm"][FONT=Times New Roman][SIZE=3][COLOR=#800080]http://www.alpertron.com.ar/ECM.htm[/COLOR][/SIZE][/FONT][/URL][SIZE=3][FONT=Times New Roman] 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.[/FONT][/SIZE]
[/QUOTE]
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 2009-03-16 18:06

RSA-99

Hi Dario.[quote=alpertron;165598]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. ...[/quote]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 2009-03-16 18:25

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 2009-03-16 20:49

[quote=10metreh;165621]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.[/quote]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 [URL]http://www.loria.fr/~zimmerma/records/ecmnet.html[/URL] or GGFNS. It will be GGFNS for everything above RSA-170.

All times are UTC. The time now is 11:55.