20050425, 12:04  #1 
Apr 2004
Copenhagen, Denmark
1110100_{2} 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 postprocessing 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 20050425 at 12:09 
20050425, 12:19  #2 
Jun 2003
The Texas Hill Country
3^{2}·11^{2} 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? 
20050425, 12:47  #3 
"Nancy"
Aug 2002
Alexandria
2467_{10} 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 
20050425, 13:53  #4 
Apr 2004
Copenhagen, Denmark
2^{2}×29 Posts 
Alex, what polynomials did you use?
I tried the following 3: 1) f(X)=X^5+100 and g(X)=99^20*X100^20 2) f(X)=100^3*X^6+99^4 and g(X)=99^16*X100^16 3) f(X)=99^2*X^6+100^3 and g(X)=99^17*X100^17 But these polys give trash results  Cheers, Jes 
20050425, 14:02  #5 
"Nancy"
Aug 2002
Alexandria
100110100011_{2} 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 
20050425, 14:31  #6  
Apr 2004
Copenhagen, Denmark
2^{2}×29 Posts 
Quote:
That resulted in ~20sec/rel instead of ~ 0.1sec/rel when you use 29 bit large primes. Thanks for correcting my error!  Cheers, Jes 

20050425, 14:33  #7 
"Nancy"
Aug 2002
Alexandria
2,467 Posts 
You're welcome!
Alex 
20050426, 05:36  #8 
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 45digit level. If you are, I would be interested in helping out with the sieving.

20050426, 07:38  #9  
Apr 2004
Copenhagen, Denmark
2^{2}·29 Posts 
Quote:
Quote:
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:
I will send a PM to you later today with the details.  Cheers, Jes 

20050426, 07:43  #10 
"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 
20050426, 07:55  #11 
Jul 2003
So Cal
2^{2}×11×47 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 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
setting up wakeon lan attempt 4  wildrabbitt  Hardware  0  20160522 17:22 
Factorization attempt for a c110 regards Odd MultiPerfect Numbers  jchein1  Factoring  60  20061125 19:38 
Idea about 10,000,000 digit attempt.  jasong  Programming  4  20051129 22:24 
Factorization attempt for a c214 regards Odd Perfect Numbers  jchein1  Factoring  14  20051015 20:01 
Factorization attempt to a c163  a new Odd Perfect Number roadblock  jchein1  Factoring  30  20050530 14:43 