Time it takes to select polynomials for 154 digits

[John5788]

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.

[John5788]

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.

[fivemack]

For a 512-bit number, I would expect to devote one to two thousand CPU-hours to finding the polynomial; I don't know whether factLat.pl has remotely sensible parameters for the polynomial search for numbers of that size.

[rogue]

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 post-processing. msieve is much faster and doesn't have a bug in the ggnfs suite that often fails to find the factors.

[John5788]

Originally Posted by rogue

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 post-processing. msieve is much faster and doesn't have a bug in the ggnfs suite that often fails to find the factors.

thanks, I didn't know about the factMsieve.pl script, I just got that and am starting with it again.

I'll dig around to see if anyone has useful parameters for my number

[Batalov]

(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 gnfs-154, probably, you may want to search for a CPU-week (and expect to will have spent 20 CPU-weeks 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.

[John5788]

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:

-> =====================================================
-> Best score so far: 0.000000e+00 (goodScore=2.590000e-12)
-> =====================================================

-> 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.59E-012 > testFactor/testFactor.polsel.-gentoo1.22958.log
-> =====================================================
-> Best score so far: 0.000000e+00 (goodScore=2.590000e-12)
-> =====================================================

-> 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.59E-012 > testFactor/testFactor.polsel.-gentoo1.22958.log
-> =====================================================
-> Best score so far: 0.000000e+00 (goodScore=2.590000e-12)
-> =====================================================

-> 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.59E-012 > testFactor/testFactor.polsel.-gentoo1.22958.log
-> =====================================================
-> Best score so far: 0.000000e+00 (goodScore=2.590000e-12)
-> =====================================================

-> 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.59E-012 > testFactor/testFactor.polsel.-gentoo1.22958.log

the fact it hasnt found anything yet has me worried.

[Batalov]

You may want to use the ladder principle. What you are trying to do is jump 7-ft high. Not a world record, but still challenging, if you have never tried to pass the 6-ft high jump. Have you?

First, try the tests included with the source.
Second, try an easy GNFS, say a 123-digit. That's merely a day-long 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 GNFS-130 (there's plenty of them there), then GNFS-140, and then...

Disregard, if you've already done these excercises.

Serge

[John5788]

Originally Posted by Batalov

You may want to use the ladder principle. What you are trying to do is jump 7-ft high. Not a world record, but still challenging, if you have never tried to pass the 6-ft high jump. Have you?

First, try the tests included with the source.
Second, try an easy GNFS, say a 123-digit. That's merely a day-long 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 GNFS-130 (there's plenty of them there), then GNFS-140, and then...

Disregard, if you've already done these excercises.

Serge

well I haven't been to that exact site to try factoring numbers, but I have tried a few sample RSA100 numbers which took less than a day to complete

[bsquared]

Originally Posted by John5788

well I haven't been to that exact site to try factoring numbers, but I have tried a few sample RSA100 numbers which took less than a day to complete

There is a *big* difference between 100 digit and 154 digit GNFS. I'd recommend trying something in between first, if you haven't already. The odd perfect number search also has smallish GNFS targets: http://oddperfect.org/composites.html

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.

[John5788]

I lowered e to 2.00e-12 and the first polynomial was found pretty early:

-> =====================================================
-> Best score so far: 0.000000e+00 (goodScore=2.000000e-12)
-> =====================================================

-> 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.00E-012 > testFactor/testFactor.polsel.-gentoo1.16383.log
M: 6345804928334754720431658612586053227344434344621313816572578856699293063157369614971879920373432240149347818163172848912889130278051942057123943802252773
Murphy_E: 2.24e-12
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.240000e-12 (goodScore=2.000000e-12)
-> =====================================================

-> 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.00E-012 > testFactor/testFactor.polsel.-gentoo1.16383.log