mersenneforum.org Factorization attempt on 100^99+99^100
 Register FAQ Search Today's Posts Mark Forums Read

 2005-04-25, 12:04 #1 JHansen     Apr 2004 Copenhagen, Denmark 11101002 Posts Factorization attempt on 100^99+99^100 Hi everyone! I'm currently factoring a number from the Cunningham project together with Tom Cage. When that's done I would like to try something new, namely a C150+ GNFS. 100^99+99^100 is ideal for this. The cofactor of 100^99+99^100 is a C151. Today I did some trial sieving with the various SNFS polynomials this number allows, but they are all terrible. By far, I got the best results using a GNFS polynomial instead. The usual rule of thumb says that one should do ECM to 1/3 of the number of digits before running GNFS, so this number needs to have ECM done to 50 digits. Therefore I would like to suggest this number for ECM work. The XYYXF homepage says there's been done 400 curves with B1=100M, so there's still a lot of work left Anyone interested in helping out? After the ECM has been done there's the 'small' matter of actually doing the GNFS sieving. This is another place where it's easy to help out, since the ggnfs siever can be used (the post-processing will not be done with ggnfs, though). If anyone is interested in helping out, then their help is most valued -- Cheers, Jes Last fiddled with by JHansen on 2005-04-25 at 12:09
 2005-04-25, 12:19 #2 Wacky     Jun 2003 The Texas Hill Country 32·112 Posts Whether done by GNFS or SNFS, the ECM work should be done first. Therefore I encourage this effort. Jes, I'm somewhat surprised that you found GNFS significantly better than SNFS. Would you mind posting some of the details of your trials?
 2005-04-25, 12:47 #3 akruppa     "Nancy" Aug 2002 Alexandria 46438 Posts Using the SNFS polynomial you mentioned before with Franke's lattice siever on an Athlon XP 3000+, I get an estimate for the sieving time of about 3 weeks. I cannot believe that GNFS on a c150 would be faster than this. Alex
 2005-04-25, 13:53 #4 JHansen     Apr 2004 Copenhagen, Denmark 22·29 Posts Alex, what polynomials did you use? I tried the following 3: 1) f(X)=X^5+100 and g(X)=99^20*X-100^20 2) f(X)=100^3*X^6+99^4 and g(X)=99^16*X-100^16 3) f(X)=99^2*X^6+100^3 and g(X)=99^17*X-100^17 But these polys give trash results -- Cheers, Jes
 2005-04-25, 14:02 #5 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts I used your 1) polynomial. This is my siever input file: Code: 2537196124785405629298472350522359111855410046873849968728166881265356084210413204319061258004615655191075511741881238499654058298331798022820025835261 X5 1 X0 100 Y1 8179069375972308708891986605443361898001 Y0 -10000000000000000000000000000000000000000 M 1320467787210331522376990713761285618785472848090779503074046958635251860331885809596723875650972264555150295702904709620129364887501601327334053746078 0 10000000 2.7 29 57 0 10000000 2.7 29 57 Alex
2005-04-25, 14:31   #6
JHansen

Apr 2004
Copenhagen, Denmark

1648 Posts

Quote:
 Originally Posted by akruppa I used your 1) polynomial. This is my siever input file: ...
I just did some sanity checking to see where my error was. I used the ggnfs version of the Franke siever. It turns out that I forgot to set the large primes limit in my input file, and it looks like the siever then assumed that I did not want to use large primes.

That resulted in ~20sec/rel instead of ~ 0.1sec/rel when you use 29 bit large primes.

Thanks for correcting my error!

--
Cheers,
Jes

 2005-04-25, 14:33 #7 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts You're welcome! Alex
 2005-04-26, 05:36 #8 trilliwig     Oct 2004 tropical Massachusetts 3×23 Posts So, are you still interested in doing 99^100+100^99? Seeing as it's now a C202 SNFS instead of a C151 GNFS. So according to the 2/9 rule, ECM need only be done up to the 45-digit level. If you are, I would be interested in helping out with the sieving.
2005-04-26, 07:38   #9
JHansen

Apr 2004
Copenhagen, Denmark

11101002 Posts

Quote:
 Originally Posted by trilliwig So, are you still interested in doing 99^100+100^99? Seeing as it's now a C202 SNFS instead of a C151 GNFS.
Yes, I am.

Quote:
 Originally Posted by trilliwig So according to the 2/9 rule, ECM need only be done up to the 45-digit level. If you are, I would be interested in helping out with the sieving.
Err... 151*2/9 ~33,6 so, the ECM needs only be done through the 35 digit level, right?

The XYYXF page states that 400 curves with B1=100M has been done, and ecm 6 reports that one needs only 25 curves with B1=100M to complete the 35 digit level. Thus, the ECM works is all done.
Quote:
 Originally Posted by trilliwig If you are, I would be interested in helping out with the sieving.
Excellent! Yes, you are most welcome!

I will send a PM to you later today with the details.

--
Cheers,
Jes

 2005-04-26, 07:43 #10 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts The GNFS 1/3 rule refers to the size of the remaining cofactor, but the SNFS 2/9 rule refers to the SNFS difficulty. The size of the cofactor has pracically no effect on the time required for SNFS. I, too, would recommend ECM to 45 digits. Alex
 2005-04-26, 07:55 #11 frmky     Jul 2003 So Cal 2×1,097 Posts That makes much more sense! At the 55 digit level, one curve with B1=11e7 takes just under 30 minutes on my 1.9GHz Opteron, so it would take nearly a year to finish at that level for my Opteron. I know SNFS or GNFS won't take nearly that long! :-) Greg

 Similar Threads Thread Thread Starter Forum Replies Last Post wildrabbitt Hardware 0 2016-05-22 17:22 jchein1 Factoring 60 2006-11-25 19:38 jasong Programming 4 2005-11-29 22:24 jchein1 Factoring 14 2005-10-15 20:01 jchein1 Factoring 30 2005-05-30 14:43

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

Mon Oct 25 08:12:08 UTC 2021 up 94 days, 2:41, 0 users, load averages: 1.30, 1.41, 1.25