20080820, 18:06  #1 
Aug 2008
127.0.0.1
7 Posts 
Time it takes to select polynomials for 154 digits
I am trying to factor a 154 digit number using GGNFS and msieve on a core 2 quad CPU with gentoo linux.
i compiled the binaries with the latest GGNFS snapshot with make nocona for 64bit binaries. now my question is, how long should the polynomial selection take using the factLat.pl script? I've left the thing running for about 8 hours and it has not found anything. however, when I was using the 32bit binaries from the stable release, the script had at least found some polynomials, but I suppose the score wasn't good enough so it continued the search. 
20080820, 21:59  #2 
Aug 2008
127.0.0.1
7_{10} Posts 
Here is what I have in my .n file
name: testfactor n: 8224973201493734039216932833462996815932154044113673505636726252834676063695616729466358005376619469264571014058650019804568205019013693877262015651491183 deg: 5 I set factLat.pl to use the kleinjung/franke poly select code. 
20080820, 22:10  #3 
(loop (#_fork))
Feb 2006
Cambridge, England
1100100110110_{2} Posts 
For a 512bit number, I would expect to devote one to two thousand CPUhours to finding the polynomial; I don't know whether factLat.pl has remotely sensible parameters for the polynomial search for numbers of that size.

20080820, 22:31  #4 
"Mark"
Apr 2003
Between here and the
2^{4}·11·41 Posts 
You should consider doing a couple of things before using factLat.pl. First, post in the ggnfs group on Yahoo. Someone might have collected some meaningful (re: useful) parameters for composites of that size. Second, use factMsieve.pl. It still sieves with the ggnfs lattice siever, but uses msieve for postprocessing. msieve is much faster and doesn't have a bug in the ggnfs suite that often fails to find the factors.

20080820, 22:51  #5  
Aug 2008
127.0.0.1
7 Posts 
Quote:
I'll dig around to see if anyone has useful parameters for my number 

20080821, 05:02  #6 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
10182_{10} Posts 
(the following thoughts are not mine):
There's a rule of thumb that you may want to spend ~5% of your full expected job time on searching for the gnfs polynomial. Of course, it's a circular argument  and you would need to have a good feeling about that final time. For a gnfs154, probably, you may want to search for a CPUweek (and expect to will have spent 20 CPUweeks for the whole job). That's optimistic, actually. Double that. Note: my CPUs are Opterons (timescale ~= 3 in the ggnfs.log parlance); look in your recent ggnfs.log for your timescale. Last fiddled with by Batalov on 20080821 at 05:24 Reason: e.g. "Scaled time: 2606.45 units (timescale=2.952)." 
20080821, 19:01  #7 
Aug 2008
127.0.0.1
7_{16} Posts 
well supposedly, the kleinjung/franke code has acceptable parameters for a 154 digit number in polynomial selection. the code has been running for almost 20 hours now without anything found yet. here is a snippet of the output:
Code:
> ===================================================== > Best score so far: 0.000000e+00 (goodScore=2.590000e12) > ===================================================== > Searching leading coefficients from 9448001 to 9449000. => "../bin/pol51m0b" b testFactor/testFactor.polsel.gentoo1.22958 v v p 7 n 4.86E+023 a 9448 A 9449 > testFactor/testFactor.polsel.gentoo1.22958.log => "../bin/pol51opt" b testFactor/testFactor.polsel.gentoo1.22958 v v n 6.13E+021 N 1.48E+019 e 2.59E012 > testFactor/testFactor.polsel.gentoo1.22958.log > ===================================================== > Best score so far: 0.000000e+00 (goodScore=2.590000e12) > ===================================================== > Searching leading coefficients from 9449001 to 9450000. => "../bin/pol51m0b" b testFactor/testFactor.polsel.gentoo1.22958 v v p 7 n 4.86E+023 a 9449 A 9450 > testFactor/testFactor.polsel.gentoo1.22958.log => "../bin/pol51opt" b testFactor/testFactor.polsel.gentoo1.22958 v v n 6.13E+021 N 1.48E+019 e 2.59E012 > testFactor/testFactor.polsel.gentoo1.22958.log > ===================================================== > Best score so far: 0.000000e+00 (goodScore=2.590000e12) > ===================================================== > Searching leading coefficients from 9450001 to 9451000. => "../bin/pol51m0b" b testFactor/testFactor.polsel.gentoo1.22958 v v p 7 n 4.86E+023 a 9450 A 9451 > testFactor/testFactor.polsel.gentoo1.22958.log => "../bin/pol51opt" b testFactor/testFactor.polsel.gentoo1.22958 v v n 6.13E+021 N 1.48E+019 e 2.59E012 > testFactor/testFactor.polsel.gentoo1.22958.log > ===================================================== > Best score so far: 0.000000e+00 (goodScore=2.590000e12) > ===================================================== > Searching leading coefficients from 9451001 to 9452000. => "../bin/pol51m0b" b testFactor/testFactor.polsel.gentoo1.22958 v v p 7 n 4.86E+023 a 9451 A 9452 > testFactor/testFactor.polsel.gentoo1.22958.log => "../bin/pol51opt" b testFactor/testFactor.polsel.gentoo1.22958 v v n 6.13E+021 N 1.48E+019 e 2.59E012 > testFactor/testFactor.polsel.gentoo1.22958.log the fact it hasnt found anything yet has me worried. 
20080821, 20:03  #8 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
10011111000110_{2} Posts 
You may want to use the ladder principle. What you are trying to do is jump 7ft high. Not a world record, but still challenging, if you have never tried to pass the 6ft high jump. Have you?
First, try the tests included with the source. Second, try an easy GNFS, say a 123digit. That's merely a daylong job. You can take one from here, for example  http://hpcgi2.nifty.com/m_kamada/f/c.cgi?q=37773_174 Usually, you can also find an easier number there  they are added every week or so (this is an easiest GNFS there at this moment). For the testing purposes, you may take a shorter number and do GNFS on it, even though SNFS will be faster (there are some on that site) Then try a GNFS130 (there's plenty of them there), then GNFS140, and then... Disregard, if you've already done these excercises. Serge 
20080821, 20:19  #9  
Aug 2008
127.0.0.1
7 Posts 
Quote:


20080821, 21:13  #10  
"Ben"
Feb 2007
2^{2}·941 Posts 
Quote:
That said, it looks like your a and A are too small by an order of magnitude or so. You could also lower e, to display more of the output of pol51opt.  ben. 

20080821, 22:07  #11 
Aug 2008
127.0.0.1
7 Posts 
I lowered e to 2.00e12 and the first polynomial was found pretty early:
Code:
> ===================================================== > Best score so far: 0.000000e+00 (goodScore=2.000000e12) > ===================================================== > Searching leading coefficients from 341001 to 342000. => "../bin/pol51m0b" b testFactor/testFactor.polsel.gentoo1.16383 v v p 7 n 4.86E+023 a 341 A 342 > testFactor/testFactor.polsel.gentoo1.16383.log => "../bin/pol51opt" b testFactor/testFactor.polsel.gentoo1.16383 v v n 6.13E+021 N 1.48E+019 e 2.00E012 > testFactor/testFactor.polsel.gentoo1.16383.log M: 6345804928334754720431658612586053227344434344621313816572578856699293063157369614971879920373432240149347818163172848912889130278051942057123943802252773 Murphy_E: 2.24e12 Y0: 474476921671002389987129456480 Y1: 264677853183412867 alpha: 6.96 c0: 45436887182203702187613529219004158389 c1: 9618343556994505527608625494947 c2: 121412576663303375538788791 c3: 23859647401868808903 c4: 46472546111430 c5: 342000 norm: 1.23e+22 skewness: 1811932.11 > ===================================================== > Best score so far: 2.240000e12 (goodScore=2.000000e12) > ===================================================== > Searching leading coefficients from 342001 to 343000. => "../bin/pol51m0b" b testFactor/testFactor.polsel.gentoo1.16383 v v p 7 n 4.86E+023 a 342 A 343 > testFactor/testFactor.polsel.gentoo1.16383.log => "../bin/pol51opt" b testFactor/testFactor.polsel.gentoo1.16383 v v n 6.13E+021 N 1.48E+019 e 2.00E012 > testFactor/testFactor.polsel.gentoo1.16383.log Last fiddled with by John5788 on 20080821 at 22:25 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
YAFU Poly Select Deadline  amphoria  YAFU  22  20160917 09:47 
msieve poly select: choosing Stage1norm  VBCurtis  Msieve  0  20160411 21:33 
Starting NFS skipping poly select  jux  YAFU  5  20160102 01:01 
ECM Takes far longer than estimated time  Rhyled  PrimeNet  31  20110206 16:46 
Wasting time at 100 digits  fivemack  Factoring  0  20100806 15:13 