mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2008-08-20, 18:06   #1
John5788
 
Aug 2008
127.0.0.1

7 Posts
Default 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.
John5788 is offline   Reply With Quote
Old 2008-08-20, 21:59   #2
John5788
 
Aug 2008
127.0.0.1

716 Posts
Default

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.
John5788 is offline   Reply With Quote
Old 2008-08-20, 22:10   #3
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

6,323 Posts
Default

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.
fivemack is offline   Reply With Quote
Old 2008-08-20, 22:31   #4
rogue
 
rogue's Avatar
 
"Mark"
Apr 2003
Between here and the

2×5×601 Posts
Default

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.
rogue is offline   Reply With Quote
Old 2008-08-20, 22:51   #5
John5788
 
Aug 2008
127.0.0.1

1112 Posts
Default

Quote:
Originally Posted by rogue View Post
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
John5788 is offline   Reply With Quote
Old 2008-08-21, 05:02   #6
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23C816 Posts
Default

(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.

Last fiddled with by Batalov on 2008-08-21 at 05:24 Reason: e.g. "Scaled time: 2606.45 units (timescale=2.952)."
Batalov is offline   Reply With Quote
Old 2008-08-21, 19:01   #7
John5788
 
Aug 2008
127.0.0.1

78 Posts
Default

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.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.
John5788 is offline   Reply With Quote
Old 2008-08-21, 20:03   #8
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23C816 Posts
Default

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
Batalov is offline   Reply With Quote
Old 2008-08-21, 20:19   #9
John5788
 
Aug 2008
127.0.0.1

1112 Posts
Default

Quote:
Originally Posted by Batalov View Post
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
John5788 is offline   Reply With Quote
Old 2008-08-21, 21:13   #10
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2×3×557 Posts
Default

Quote:
Originally Posted by John5788 View Post
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.
bsquared is offline   Reply With Quote
Old 2008-08-21, 22:07   #11
John5788
 
Aug 2008
127.0.0.1

7 Posts
Default

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


Code:
-> =====================================================
-> 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

Last fiddled with by John5788 on 2008-08-21 at 22:25
John5788 is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
YAFU Poly Select Deadline amphoria YAFU 22 2016-09-17 09:47
msieve poly select: choosing Stage1norm VBCurtis Msieve 0 2016-04-11 21:33
Starting NFS skipping poly select jux YAFU 5 2016-01-02 01:01
ECM Takes far longer than estimated time Rhyled PrimeNet 31 2011-02-06 16:46
Wasting time at 100 digits fivemack Factoring 0 2010-08-06 15:13

All times are UTC. The time now is 17:42.

Sat Nov 28 17:42:08 UTC 2020 up 79 days, 14:53, 3 users, load averages: 1.53, 1.38, 1.47

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.