mersenneforum.org Seeking GNFS factoring advice...
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

 2012-03-04, 03:24 #1 WraithX     Mar 2006 23·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.93e-014 to 6.82e-014 And after one day of searching it had already found: # norm 1.272995e-017 alpha -7.538674 e 8.176e-014 rroots 5 So far it has been running for 8 days and the top 5 polynomial scores are: # norm 1.174441e-017 alpha -7.685977 e 7.761e-014 rroots 3 # norm 1.209393e-017 alpha -6.405035 e 7.802e-014 rroots 5 # norm 1.207379e-017 alpha -7.589093 e 7.894e-014 rroots 3 # norm 1.280555e-017 alpha -8.747171 e 8.159e-014 rroots 3 # norm 1.272995e-017 alpha -7.538674 e 8.176e-014 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 gnfs-lasieve4I15e (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?
 2012-03-04, 04:45 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 216468 Posts The polys already look good, but you will need about 2000 CPU-days for sieving (I've applied a correction for the newest CPUs - divided my old estimates by two) and a month for algebra on one 4-or-6-core. How many cores do you have? Say, for three six-cores, that's 111 days. Are you ready for that?
2012-03-04, 10:02   #3
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

2×29×109 Posts

Quote:
 Originally Posted by WraithX 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.
How large is your previous largest GNFS factorisation?

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^421-1 C180 I used 15e and

Code:
lpbr: 31
lpba: 32
mfbr: 62
mfba: 64
alambda: 2.6
rlambda: 2.6
alim: 150000000
rlim: 80000000
and sieved Q=40e6 .. 340e6 but you should certainly try variants on these parameters ... basically try to optimise time-per-relation under the constraint that you get between 15000 and 30000 relations from a Q-range of 1e4. You should also try

lpba: 31
mfba: 93
alambda: 3.6

and re-optimise alim/rlim to get the speed as good as possible, and see if that can compete.

5^421-1 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 i7-3930

Last fiddled with by fivemack on 2012-03-04 at 10:03

 2012-03-04, 10:17 #4 debrouxl     Sep 2009 977 Posts Yeah, for a GNFS task of that difficulty, 14e won't do the job efficiently...
2012-03-04, 14:32   #5
WraithX

Mar 2006

1110110002 Posts

Quote:
 How many cores do you have? Say, for three six-cores, that's 111 days. Are you ready for that?
I currently have a dual quad core Xeon machine with 12GB of ram, and I have just ordered the parts for a dual six core Xeon machine with 48GB of ram. So, for this project I'll have 20 cores. And yes, 111 days is much less than the time I've already spent on ECM on this number.

Quote:
 Originally Posted by fivemack How large is your previous largest GNFS factorisation?
It looks like my previous largest was a C139.

Quote:
 Originally Posted by fivemack 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. and sieved Q=40e6 .. 340e6 but you should certainly try variants on these parameters ... basically try to optimise time-per-relation under the constraint that you get between 15000 and 30000 relations from a Q-range of 1e4. 5^421-1 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 i7-3930
Thank you for all of the parameter advice. When I get my new machine up and running I'll start 12 more poly selects and see if anything better comes up. [as long as the machine survives 24h of Prime95 torture tests, that is ]

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?

 2012-03-04, 15:20 #6 fivemack (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 test-sieving 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 CPU-year sieving so you should be able to do all the steps within two weeks.
2012-03-04, 18:53   #7
WraithX

Mar 2006

23·59 Posts

Quote:
 Originally Posted by fivemack 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 CPU-year sieving so you should be able to do all the steps within two weeks.
Hmmm, okay, but then what are the recommended parameters to factor a C160? Should I use the 14e or the 15e siever?

Should I factor one of the homogeneous Cunningham's with GNFS? I'd like to do either 3^505-2^505 or 3^515-2^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?

 2012-03-04, 19:12 #8 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 2×33×132 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 ~230-235. For GNFS: e.g. L(1354) or L(1378) For SNFS: I(1097) (first hole - can be done as a GNFS, too!), I(1117)
 2012-03-04, 19:46 #9 debrouxl     Sep 2009 977 Posts I know that for Aliquot team sievings, people tend to use 14e below difficulty 162-163, 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 30-bit large primes. For the sake of making a record, 31-bit 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 BOINC-based 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
2012-03-04, 19:57   #10
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

2·29·109 Posts

Quote:
 Originally Posted by WraithX Hmmm, okay, but then what are the recommended parameters to factor a C160? Should I use the 14e or the 15e siever? Should I factor one of the homogeneous Cunningham's with GNFS? I'd like to do either 3^505-2^505 or 3^515-2^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?
14e is enough for a C160; they take about half a CPU-year on my 1.9GHz Opteron.

It would be silly to try those particular homogeneous Cunninghams with GNFS, they're easier with SNFS - you want a number where the GNFS-difficulty is displayed in green, say 5^356+2^356.

2012-03-04, 20:21   #11
xilman
Bamboozled!

"𒉺𒌌𒇷𒆷𒀭"
May 2003
Down not across

2×3×7×241 Posts
Shameless plug

Quote:
 Originally Posted by fivemack 14e is enough for a C160; they take about half a CPU-year on my 1.9GHz Opteron. It would be silly to try those particular homogeneous Cunninghams with GNFS, they're easier with SNFS - you want a number where the GNFS-difficulty is displayed in green, say 5^356+2^356.
I support Tom's recommendation because I seem to have inherited those tables. Tom is running their reservation system.

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 2012-03-04 at 20:23

 Thread Tools

 Similar Threads Thread Thread Starter Forum Replies Last Post BotXXX Factoring 25 2015-09-02 08:27 WraithX Factoring 59 2013-07-30 01:13 Syd Aliquot Sequences 7 2011-03-14 18:35 jasong Factoring 3 2006-10-24 04:43 ixfd64 Factoring 1 2004-04-27 09:41

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

Sun Oct 25 05:08:44 UTC 2020 up 45 days, 2:19, 0 users, load averages: 2.16, 1.81, 1.64

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.