New polynomial finder discussion - Page 2

Andi47 · 2008-11-23, 17:53

I have searched gnfs polynomials for 10,7,167+ c120 both with msieve and pol5m0b / pol51opt and got:

msieve was running for approx. 3 hours (it was suppost to run 3,75 hours, but since my pc was in standby mode for a while, msieve stopped after ~3 hours. (due to the standby, it assumed that >6 hours have passed)

Code:

n: 223647331337501130642693578497501842426733748444730351702780813709242741096431450273917668186036117236877146296909317487 
skew: 278365.97
c5  4500
c4 -212993220
c3 -861252344721509
c2  91932264615385941392
c1  39678464140799797940413876
c0 -5558888226976215535514572574080
Y0 -137806723240087021239057
Y1  5526556814339
rlim: 4500000
alim: 4500000
lpbr: 27
lpba: 27
rlambda: 2.4
alambda: 2.4
mfbr: 50
mfba: 50

I searched with pol51m0b and pol51opt from 100 to 37000 (-a 1 -A 37) with default parameters and got:

Code:

n: 223647331337501130642693578497501842426733748444730351702780813709242741096431450273917668186036117236877146296909317487 
skew: 129270.14
c5 5940
c4 2212877286
c3 757945017884750
c2 -43808229801530166427
c1 -4963828809351559226374000
c0 200737898093678577808713735792
Y1 188517494347
Y0 -130363318812083573947967
rlim: 4500000
alim: 4500000
lpbr: 27
lpba: 27
rlambda: 2.4
alambda: 2.4
mfbr: 50
mfba: 50

searching with gnfs-lasieve4I13e from Q=4500000 to 4505000 yielded (on a P4 @ 3.4 GHz)

with the msieve-polynomial: total yield: 21536, Q=4505003 (0.03123 sec/rel)

with the poly found by pol51opt: total yield: 18069, Q=4505003, (0.03581 sec/rel)

nice!!

jasonp · 2008-11-23, 19:29

Good. Note that plugging the GGNFS-generated polynomial into msieve and pretending to start the sieving, I get a combined score of 1.503018e-011, and the ratio of the two combined scores is 1.27, so by that estimate the msieve-generated polynomial should be generating 27% more relations (it manages 19% more).

Speedups of this magnitude are approximately in line with what Kleinjung has found for huge size problems.

frmky · 2008-11-23, 19:31

Quote:

Originally Posted by jasonp

Does GGNFS also need the value of M when given a non-monic rational polynomial, or is M calculated?

No, given the coefficients GGNFS will calculate the value of M.

Batalov · 2008-11-23, 22:09

I am running a small side-by-side with pol51 test, too, and so far, so good, but here's a couple small questions:
1. I get a lot of "expand failed" - is it bad?
2. In the growing .dat.p I see some fairly good polys. One of them has "e inf".

Code:

# norm 1.184e+17 alpha -6.742380 (cool!) skew 247698.68 e 1.641e-11
R0 -94599565619720927453193
R1  4290604665773
A0 -2369052967904104373321209604240
A1 -76732717132887409987838332
A2 -361067069045307995158
A3  1444601004414064
A4  3835821375
A5  4500
# norm 1.192e+17 alpha -5.720751 skew 304638.57 e inf (Heh?)
R0 -94599833825418584923423
R1  4290604665773
A0  22765341350007496195942257827712
A1 -61200475746285665445037692
A2 -553031906855276999590
A3  661329732309064
A4  2429346375
A5  4500

fivemack · 2008-11-23, 22:46

Quote:

Originally Posted by jasonp

Sorry that I skipped some details:

- if you build from source with no makefile arguments, you get the old (known working) nonskewed-polynomial selector, which is very sucky. To get the new polynomial finder you need to run make with GMP=1 or ECM=1 (which expects the GMP library to be available, and allows the new poly finder to get built).

When I do 'make x86_64 GMP=1', I get a load of warnings like

gnfs/poly/stage2/root_sieve.c:622: warning: passing argument 4 of ‘save_rotation’ with different width due to prototype

and a failure to link because

poly.c:(.text+0x2a8): undefined reference to `find_poly_noskew'

Phil MjX · 2008-11-23, 22:49

hi !

I have problems with the time limit with the poly selection : with v1.38, msieve found an excellent poly with the index 111960 (just for info, a 25% better score) whereas the v1.39beta didn't find it with the hardcoded 400 sec limits at the same index...
pol5 may be very slow for interesting index values and, with my laptop pentium M, 400 sec seems to be too short !

I would also have the request to have the ability change the multiplier by the command line since 12,48,720...may be adapted to the size of the composite you try to factorize...

And, thanks for all the time you spend for completing msieve gnfs !

jasonp · 2008-11-23, 23:38

Serge: the polynomial rating code is very different (much faster) than the code in pol5, and has to perform a very difficult numerical integration. The integrator works 99% of the time, but there are cases where it fails.

Tom: you have to run 'make clean' when switching to ECM=1 or GMP=1, because the makefile dependencies don't realize that gnfs/poly/poly.o needs to be rebuilt because it wanted the noskew poly finder before but the skewed finder is all that's available now. I haven't even compiled in a 64-bit environment, so the warnings are unsurprising (hopefully they're all harmless).

Philippe: you have to understand that the old and new poly finder are very different, and in general will not find the same polynomials. The search space used by the new finder is much larger, which makes it possible to find better polynomials, but this is not assured. The problem is that you can spend weeks searching for a good poly for even a single leading coefficient with the new finder, but the time limit for abandoning the poly selection and getting on with the sieving has not changed. Maybe both algorithms can be run on inputs, I don't know if it's better to arrange that.

Thanks for all the feedback, beta-2 will be out in the next few days.

Batalov · 2008-11-24, 00:00

Yes, the e estimate failure was just one out of 76 so far, so your 99% estimate holds water.

(I hate overblown claims!)

Tom, Jason: with a fresh libgmp 4.2.4 and ecm 6.2.1 msieve builds, but yes, there are a few warnings. ~70 (times two) about gmp*.h proto mismatches and 15 of msieve itself:

Code:

common/fastmult.c:73: warning: passing argument 1 of 'dd_clear_precision' with different width due to prototype
gnfs/poly/poly.c:218: warning: passing argument 1 of 'dd_clear_precision' with different width due to prototype
gnfs/poly/stage1/stage1_roots.c:174: warning: passing argument 2 of 'mp_gcd_1' with different width due to prototype
gnfs/poly/stage1/stage1_roots.c:224: warning: passing argument 3 of 'memset' with different width due to prototype
gnfs/poly/stage2/optimize.c:50: warning: comparison between signed and unsigned
gnfs/poly/stage2/optimize.c:364: warning: passing argument 4 of 'evaluate' as unsigned due to prototype
gnfs/poly/stage2/optimize.c:411: warning: passing argument 9 of 'minimize_line_core' as signed due to prototype
gnfs/poly/stage2/optimize.c:525: warning: passing argument 2 of 'optimize_local' as unsigned due to prototype
gnfs/poly/stage2/optimize.c:592: warning: passing argument 2 of 'optimize_local' as unsigned due to prototype
gnfs/poly/stage2/root_sieve.c:427: warning: comparison between signed and unsigned
gnfs/poly/stage2/root_sieve.c:509: warning: comparison between signed and unsigned
gnfs/poly/stage2/root_sieve.c:520: warning: passing argument 3 of 'save_lattice' with different width due to prototype
gnfs/poly/stage2/root_sieve.c:622: warning: passing argument 4 of 'save_rotation' with different width due to prototype
gnfs/poly/stage2/root_sieve.c:644: warning: passing argument 5 of 'prepare_sieve_lattice' as unsigned due to prototype
gnfs/poly/stage2/root_sieve.c:663: warning: passing argument 4 of 'save_rotation' with different width due to prototype

Just in case.
--S

jasonp · 2008-11-24, 01:22

All those warnings look harmless, though I'll fix them before the full release.

Batalov · 2008-11-24, 01:35

Quote:

Originally Posted by jasonp

Yes, that's the best one found. Printing the skew is easy, I'll throw it in.

Does GGNFS also need the value of M when given a non-monic rational polynomial, or is M calculated?

Is it really the best? I am not sure. After the 3.5 hour run, I've got this in msieve.log:

Code:

Sun Nov 23 13:17:01 2008  Msieve v. 1.39
Sun Nov 23 13:17:01 2008  random seeds: 555f1db5 48bf7f70
Sun Nov 23 13:17:01 2008  factoring 34093769070263942955503177408570636568154822681818558606509181335014782811074308996491335063579593027737149761680752317 (119 digits)
Sun Nov 23 13:17:02 2008  searching for 15-digit factors
Sun Nov 23 13:17:02 2008  commencing number field sieve (119-digit input)
Sun Nov 23 13:17:02 2008  commencing number field sieve polynomial selection
Sun Nov 23 13:17:02 2008  time limit set to 3.38 hours
Sun Nov 23 13:17:02 2008  searching leading coefficients from 3532 to 33782
Sun Nov 23 16:48:48 2008  polynomial selection complete
Sun Nov 23 16:48:48 2008  R0: -94599833825418584923423
Sun Nov 23 16:48:48 2008  R1:  4290604665773
Sun Nov 23 16:48:48 2008  A0:  22765341350007496195942257827712
Sun Nov 23 16:48:48 2008  A1: -61200475746285665445037692
Sun Nov 23 16:48:48 2008  A2: -553031906855276999590
Sun Nov 23 16:48:48 2008  A3:  661329732309064
Sun Nov 23 16:48:48 2008  A4:  2429346375
Sun Nov 23 16:48:48 2008  A5:  4500
Sun Nov 23 16:48:48 2008  size score = 1.606673e-12, Murphy alpha = -5.720751, combined = 1.081661e-11
Sun Nov 23 16:48:48 2008  elapsed time 03:31:47

but in .dat.p:

Code:

/32227_193> grep alpha msieve.dat.p | sort +8rg |head
# norm 1.192e+17 alpha -5.720751 skew 304638.57 e inf
# norm 6.915e+16 alpha -7.327632 skew 142699.88 e 2.169e-11
# norm 1.024e+17 alpha -7.188147 skew 286008.56 e 1.963e-11
# norm 3.412e+16 alpha -5.783876 skew 230819.08 e 1.931e-11
# norm 1.008e+17 alpha -6.984801 skew 125132.25 e 1.921e-11
# norm 1.782e+17 alpha -7.335323 skew 270846.25 e 1.909e-11
# norm 1.078e+17 alpha -6.842652 skew 136306.69 e 1.905e-11
# norm 5.488e+16 alpha -6.747836 skew 85282.64 e 1.904e-11
# norm 9.217e+16 alpha -7.104571 skew 200951.91 e 1.894e-11
# norm 3.302e+16 alpha -6.437370 skew 74098.66 e 1.869e-11

Well, disregarding the e=inf, there's an excellent poly, which has much both better alpha and e than that in msieve.log. So I used it and it is 15% faster than the pol51-generated in 4 hours:

Code:

name: 32227_193
# it is the 119-composite residue from 3222..2227 http://hpcgi2.nifty.com/m_kamada/f/c.cgi?q=32227_193
n: 34093769070263942955503177408570636568154822681818558606509181335014782811074308996491335063579593027737149761680752317
Y0: -78144654374057956235581
Y1:  3845840165363
c0: -1871596898878390306911020084352
c1: -15959543399998484701121224
c2:  195713673571504411046
c3:  1015716197615315
c4: -3952249560
c5: 11700
skew: 142699.88
# norm 6.915e+16
# alpha -7.327632
# Murphy_E 2.169e-11
# M
type: gnfs
rlim: 4500000
alim: 4500000
lpbr: 27
lpba: 27
mfbr: 50
mfba: 50
rlambda: 2.5
alambda: 2.5
qintsize: 100000

vs. pol51's

Code:

name: 32227_193
n: 34093769070263942955503177408570636568154822681818558606509181335014782811074308996491335063579593027737149761680752317
skew: 84894.10
# norm 2.34e+16
c5: 9480
c4: 5731343794
c3: 260967341061300
c2: -42181384816963855413
c1: 320867153341330567494006
c0: 15057329509837849519549992420
# alpha -5.10
Y1: 5111731326383
Y0: -81502333286757518675791
# Murphy_E 2.94e-10
# M 8340416203196397804695017049168297202376271037300591393721961293287033398978686016283029967418177785038003517372484508
type: gnfs
rlim: 4500000
alim: 4500000
lpbr: 27
lpba: 27
mfbr: 50
mfba: 50
rlambda: 2.5
alambda: 2.5
qintsize: 100000

Sieving now...

jasonp · 2008-11-24, 03:01

Grrr, the worse poly was saved because a (incorrect) score of infinity beat a correct score that was smaller. Fixing now.

2008-11-23, 22:49	#17
Phil MjX Sep 2004 5·37 Posts	hi ! I have problems with the time limit with the poly selection : with v1.38, msieve found an excellent poly with the index 111960 (just for info, a 25% better score) whereas the v1.39beta didn't find it with the hardcoded 400 sec limits at the same index... pol5 may be very slow for interesting index values and, with my laptop pentium M, 400 sec seems to be too short ! I would also have the request to have the ability change the multiplier by the command line since 12,48,720...may be adapted to the size of the composite you try to factorize... And, thanks for all the time you spend for completing msieve gnfs ! Last fiddled with by Phil MjX on 2008-11-23 at 22:52

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Polynomial Discriminant is n^k for an n-1 degree polynomial	carpetpool	Miscellaneous Math	14	2017-02-18 19:46
Polynomial algorithm	diep	Factoring	7	2012-09-29 12:09
Question about polynomial finder	jordis	Msieve	1	2009-01-10 17:58
[Need help] about Matrix Polynomial	buan	Homework Help	3	2007-07-17 15:07
Polynomial	R.D. Silverman	NFSNET Discussion	13	2005-09-16 20:07

2008-11-23, 19:29	#13
jasonp Tribal Bullet Oct 2004 3,541 Posts	Good. Note that plugging the GGNFS-generated polynomial into msieve and pretending to start the sieving, I get a combined score of 1.503018e-011, and the ratio of the two combined scores is 1.27, so by that estimate the msieve-generated polynomial should be generating 27% more relations (it manages 19% more). Speedups of this magnitude are approximately in line with what Kleinjung has found for huge size problems.

2008-11-23, 23:38	#18
jasonp Tribal Bullet Oct 2004 3,541 Posts	Serge: the polynomial rating code is very different (much faster) than the code in pol5, and has to perform a very difficult numerical integration. The integrator works 99% of the time, but there are cases where it fails. Tom: you have to run 'make clean' when switching to ECM=1 or GMP=1, because the makefile dependencies don't realize that gnfs/poly/poly.o needs to be rebuilt because it wanted the noskew poly finder before but the skewed finder is all that's available now. I haven't even compiled in a 64-bit environment, so the warnings are unsurprising (hopefully they're all harmless). Philippe: you have to understand that the old and new poly finder are very different, and in general will not find the same polynomials. The search space used by the new finder is much larger, which makes it possible to find better polynomials, but this is not assured. The problem is that you can spend weeks searching for a good poly for even a single leading coefficient with the new finder, but the time limit for abandoning the poly selection and getting on with the sieving has not changed. Maybe both algorithms can be run on inputs, I don't know if it's better to arrange that. Thanks for all the feedback, beta-2 will be out in the next few days.

2008-11-24, 01:22	#20
jasonp Tribal Bullet Oct 2004 6725₈ Posts	All those warnings look harmless, though I'll fix them before the full release.

2008-11-24, 03:01	#22
jasonp Tribal Bullet Oct 2004 3,541 Posts	Grrr, the worse poly was saved because a (incorrect) score of infinity beat a correct score that was smaller. Fixing now.