mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2012-03-04, 03:24   #1
WraithX
 
WraithX's Avatar
 
Mar 2006

47210 Posts
Default 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?
WraithX is offline   Reply With Quote
Old 2012-03-04, 04:45   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100011110010012 Posts
Default

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?
Batalov is offline   Reply With Quote
Old 2012-03-04, 10:02   #3
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

142638 Posts
Default

Quote:
Originally Posted by WraithX View Post
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
fivemack is offline   Reply With Quote
Old 2012-03-04, 10:17   #4
debrouxl
 
debrouxl's Avatar
 
Sep 2009

977 Posts
Default

Yeah, for a GNFS task of that difficulty, 14e won't do the job efficiently...
debrouxl is offline   Reply With Quote
Old 2012-03-04, 14:32   #5
WraithX
 
WraithX's Avatar
 
Mar 2006

23·59 Posts
Default

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 View Post
How large is your previous largest GNFS factorisation?
It looks like my previous largest was a C139.

Quote:
Originally Posted by fivemack View Post
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?
WraithX is offline   Reply With Quote
Old 2012-03-04, 15:20   #6
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

11000101100112 Posts
Default

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.
fivemack is offline   Reply With Quote
Old 2012-03-04, 18:53   #7
WraithX
 
WraithX's Avatar
 
Mar 2006

23×59 Posts
Default

Quote:
Originally Posted by fivemack View Post
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?
WraithX is offline   Reply With Quote
Old 2012-03-04, 19:12   #8
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

916110 Posts
Default

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)
Batalov is offline   Reply With Quote
Old 2012-03-04, 19:46   #9
debrouxl
 
debrouxl's Avatar
 
Sep 2009

11110100012 Posts
Default

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
debrouxl is offline   Reply With Quote
Old 2012-03-04, 19:57   #10
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

6,323 Posts
Default

Quote:
Originally Posted by WraithX View Post
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.
fivemack is offline   Reply With Quote
Old 2012-03-04, 20:21   #11
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

100111110101012 Posts
Default Shameless plug

Quote:
Originally Posted by fivemack View Post
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
xilman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Factoring a 1024-bit RSA with GNFS? BotXXX Factoring 25 2015-09-02 08:27
Advice for large GNFS jobs? WraithX Factoring 59 2013-07-30 01:13
need some advice: gnfs C164 from 162126:i4274 Syd Aliquot Sequences 7 2011-03-14 18:35
buying computer for factoring, looking for advice jasong Factoring 3 2006-10-24 04:43
any good GNFS factoring programs? ixfd64 Factoring 1 2004-04-27 09:41

All times are UTC. The time now is 09:04.

Mon Nov 30 09:04:41 UTC 2020 up 81 days, 6:15, 3 users, load averages: 1.14, 1.17, 1.12

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.