20120304, 03:24  #1 
Mar 2006
2^{3}·59 Posts 
Seeking GNFS factoring advice...
Hello everyone,
I've decided to try my first large GNFS factorization on a C181, and I'm looking for advice on the various steps in the process. I have been running 4 copies of msieve 1.50 to try to find a good polynomial to use. The log said: expecting poly E from 5.93e014 to 6.82e014 And after one day of searching it had already found: # norm 1.272995e017 alpha 7.538674 e 8.176e014 rroots 5 So far it has been running for 8 days and the top 5 polynomial scores are: # norm 1.174441e017 alpha 7.685977 e 7.761e014 rroots 3 # norm 1.209393e017 alpha 6.405035 e 7.802e014 rroots 5 # norm 1.207379e017 alpha 7.589093 e 7.894e014 rroots 3 # norm 1.280555e017 alpha 8.747171 e 8.159e014 rroots 3 # norm 1.272995e017 alpha 7.538674 e 8.176e014 rroots 5 Some of the things I am wondering: 1) Should I stop searching for a better poly and use one of the two best from up above? 2) Is it right that I should be using gnfslasieve4I15e (or maybe 16e)? 3) I see the polynomials are specified, but what are good choices for the other parameters? (ie, rlim,alim,lpbr,lpba,mfbr,mfba,rlambda,alambda,qintsize, and do I have to specify m?) I am planning on using the factmsieve script on two computers to help automate this, 4) How many relations should be collected before attempting filtering? 5) How do I combine relations files from the two computers? (just 'cat', or maybe msieve.add, or...) 6) How much memory will the machine need to finish all the steps of GNFS? 7) Is there anything else to consider that I might not have thought of? 
20120304, 04:45  #2 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
21646_{8} Posts 
The polys already look good, but you will need about 2000 CPUdays for sieving (I've applied a correction for the newest CPUs  divided my old estimates by two) and a month for algebra on one 4or6core. How many cores do you have? Say, for three sixcores, that's 111 days. Are you ready for that?

20120304, 10:02  #3  
(loop (#_fork))
Feb 2006
Cambridge, England
2×29×109 Posts 
Quote:
I agree with batalov that you've found a reasonably respectable polynomial, but I would probably carry on polynomial search for another three weeks or so on four CPUs  that's still only about 10% of the expected time to sieve. For 5^4211 C180 I used 15e and Code:
lpbr: 31 lpba: 32 mfbr: 62 mfba: 64 alambda: 2.6 rlambda: 2.6 alim: 150000000 rlim: 80000000 lpba: 31 mfba: 93 alambda: 3.6 and reoptimise alim/rlim to get the speed as good as possible, and see if that can compete. 5^4211 used 300 million unique relations from about 400 million raw. You just cat together the relation files and run msieve v nc1, and it all fitted in 8GB memory, the linear algebra took 891 hours on a Phenom x4 and would be a good deal quicker on an i73930 Last fiddled with by fivemack on 20120304 at 10:03 

20120304, 10:17  #4 
Sep 2009
977 Posts 
Yeah, for a GNFS task of that difficulty, 14e won't do the job efficiently...

20120304, 14:32  #5  
Mar 2006
111011000_{2} Posts 
Quote:
It looks like my previous largest was a C139. Quote:
When test sieving to find the best parameters, does it matter if I just use one start point of Q, or should I test it out at several different Q values? ie, Should I just test at Q=40e6 (+10e3) with all my different parameters, or should I test at Q=40e6,100e6,200e6,etc (+10e3)? Also, when sieving, are there any pros/cons to using large ranges? Should the range of Q be "small", like around 50e3 or 100e3, or would it be okay to use a range of 1e6 or 10e6? 

20120304, 15:20  #6 
(loop (#_fork))
Feb 2006
Cambridge, England
2·29·109 Posts 
If Qmin is less than alim, then alim is set equal to Qmin. So you are in theory missing potential relations by using large ranges when sieving with Q < alim. I have got into the habit of sieving from alim/3 to alim (obviously setting alim so that that gives enough relations), so I always sieve in small ranges.
When using 16e it's worth using very small ranges because about 0.001% of Q values cause some versions of the siever to enter an infinite loop; I've never bumped into this problem at 15e. For test sieving for a problem this big, I'd suggest * try a small Qmin to figure out how many Q you need to get 400 million relations * then do say six jobs equally spaced from Qmin to the Qmax you'll require As far as I can tell, doing a range of 10^4 Q gives you a yield accurate to about 10%, doing a range of 10^3 Q only gives it accurate to about 30% ... so don't make decisions based on only 10% differences between ranges of 10^4 Q. Of course testsieving ranges of 10^5 is starting to get a bit tedious. I really would suggest that you do a C160 to get a bit of familiarity with the hardware and software before going to the C180; a C160 needs half a CPUyear sieving so you should be able to do all the steps within two weeks. 
20120304, 18:53  #7  
Mar 2006
2^{3}·59 Posts 
Quote:
Should I factor one of the homogeneous Cunningham's with GNFS? I'd like to do either 3^5052^505 or 3^5152^515, both of which I saw at the following web site: http://www.chiark.greenend.org.uk/uc...mack/homcun.pl Is that list current? Or should I find another C160 to factor? 

20120304, 19:12  #8 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2×3^{3}×13^{2} Posts 
You can do a Fibonacci or a Lucas composite  there are gnfs jobs available in that range. Or you can do an equivalently long snfs job with difficulty ~230235.
For GNFS: e.g. L(1354) or L(1378) For SNFS: I(1097) (first hole  can be done as a GNFS, too!), I(1117) 
20120304, 19:46  #9 
Sep 2009
977 Posts 
I know that for Aliquot team sievings, people tend to use 14e below difficulty 162163, and 15e above. So for a C160, I'd say 14e
For RSALS, which has only 14e, I've cranked 14e up to 169 digits, with a good polynomial and 30bit large primes. For the sake of making a record, 31bit LPs could expand the usable range of 14e a bit further in a territory where 14e is no longer the most efficient siever  but for now, I'm not doing that. I guess I should mention the BOINCbased factoring framework described at http://www.mersenneforum.org/showthread.php?t=16114 . Maybe less fun than splitting the ranges manually and gathering the work manually, but since you have complete control of your computers, this is an option you might want to investigate, even if to reject it 
20120304, 19:57  #10  
(loop (#_fork))
Feb 2006
Cambridge, England
2·29·109 Posts 
Quote:
It would be silly to try those particular homogeneous Cunninghams with GNFS, they're easier with SNFS  you want a number where the GNFSdifficulty is displayed in green, say 5^356+2^356. 

20120304, 20:21  #11  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2×3×7×241 Posts 
Shameless plug
Quote:
Alternatively, you're welcome to try one or more of the (Homogeneous) Cullen and Woodall numbers but, again, I suggest that you pick one which is easier by GNFS than by SNFS. Paul Last fiddled with by xilman on 20120304 at 20:23 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Factoring a 1024bit RSA with GNFS?  BotXXX  Factoring  25  20150902 08:27 
Advice for large GNFS jobs?  WraithX  Factoring  59  20130730 01:13 
need some advice: gnfs C164 from 162126:i4274  Syd  Aliquot Sequences  7  20110314 18:35 
buying computer for factoring, looking for advice  jasong  Factoring  3  20061024 04:43 
any good GNFS factoring programs?  ixfd64  Factoring  1  20040427 09:41 