New polynomial finder discussion - Page 5

jasonp · 2008-11-25, 23:29

The bounds on the norm used in the new poly selector are actually the same as in v1.38. One big difference is that the root sieve in v1.39 is much more powerful than in v1.38; if the mediocre polynomials that are popping out of the 1.39 run had been found in 1.38 they would have been discarded without being saved. The selection process uses the combined size and root scores when rating polynomials. Polynomials with small size are just as rare as before, but you're seeing more of them because the root sieve is producing excellent alpha values to compensate. A fair comparison would require porting the new root sieve code back into 1.38, maybe you'd start seeing exceptional polynomials pop out faster then.

The only solution is to wait until you get good size and root properties simultaneously, and this is why poly selection takes so long. Getting lucky is the point of the exercise :)

PS: I can't say for sure, but using a larger multiplier should not make a difference to polynomial quality at all. Modern poly selection works much better because choosing a leading rational coefficient larger than one gives you more possibilities than you can ever hope to search in a reasonable time, and using a sieve to find good alpha values improves the alpha much more than using a large multiplier ever could

joral · 2008-11-26, 17:03

Quote:

Originally Posted by jasonp

Now available:
- fixed 64-bit NFS poly selection; it was completely broken

Not completely broken... I have gotten some reasonable polys out of it on my 64 bit box.

Andi47 · 2008-11-26, 17:41

Quote:

Originally Posted by jasonp

Now available:

win32 binary
source

Highlights:

- fixed 64-bit NFS poly selection; it was completely broken

- added poly skew to the factor base file format, logfile, and internal structures (not used internally, yet)

- lowered the size of most A5 coefficients that are searched, and increased the time per coefficient

- fixed almost all compile warnings

- added forgotten typo to the NFS filtering

- added more MSVC tweaks from Brian Gladman; the MSVC project will now link with GMP and GMP-ECM by default. See the readme in the build.vc9 directory if you don't want them.

The shoddy state of this beta has me peeved, but hopefully this will be the last one before a full release later in the week.

I am currently not on my home PC to check my output files from Beta1, so I have a question:

Does msieve print the range which it has searched to the outputfile when it stopps or when it is stopped? I might want to search a bit higher when msieve was stopped, or when it stopps "prematurely" because I had set my PC to standby mode overnight and it mistaktes the time passed by during sleep with elapsed search time.

jasonp · 2008-11-26, 18:51

Right now you do get a printout of each coefficient range that has been searched; as long as that hasn't scrolled off your terminal window you can see the last range searched and set the next range manually.

Batalov · 2008-11-26, 20:13

I ran two side-by-side tests: a GNFS-119 and a GNFS-121.

The integrator still fails (once; and indeed the candidate is then skipped), but the "expand failed" messages are gone. And the polynomials that were found by a Windows binary several days ago are being found by the x86_64. This bug is nailed. Thanks. So, if the integration fails to converge, then you would expect the polynomial be a dud, right? No need to fix that anytime soon, if so.

I wonder how well the GNFS-119 will fare with beta2 on x86_64 (it was already faster than pol51's with beta1, but as we know now even that poly was not the best, most likely). I will re-run it.

jasonp · 2008-11-26, 21:42

If the integrator fails, you really cannot conclude anything about the polynomial. The integrand is dx / pow( (R(x)*A(x))^2, 1/6 ) where R(x) and A(x) are the rational and algebraic polynomials, respectively, and these have very large integer coefficients that cannot be stored to full accuracy in ordinary floating point. The integration interval is broken up into distinct regions with endpoints at the polynomial roots, and I think the problems arise because those roots are not computed to sufficient accuracy. The integrator samples the integrand extremely close to the endpoints, so it's possible that a polynomial value becomes exactly zero to the limit of roundoff error, which causes the infinities that you see. Frankly I'm surprised it doesn't fail more often than it does...

bsquared · 2008-11-26, 21:59

Quote:

Originally Posted by bsquared

I'll let it run till it produces a few more polys, then test them out. I haven't done much experiementing with lower E, but better alpha, on yield, so this looks like a good chance to start.

Late beta1 results:

I let the poly finder run for 24 hrs and eventually got 7 polynomials on my C150. The best one was the first with really good alpha. However it proved to be worse than the pol51 generated poly on trial sieving (granted, over perhaps too small of an interval), even though the alpha and scaled murphy_e say it should be a slightly better performer.

Code:

% gnfs-lasieve4I14e -a 23269.53-1.poly -f 25000000 -c 1000 -o test_pol51.dat
total yield: 3303, q=25001029 (0.07250 sec/rel)
% gnfs-lasieve4I14e -a msieve.poly -f 25000000 -c 1000 -o test_msieve.dat
total yield: 2400, q=25001029 (0.07620 sec/rel)

I also note that the range over which it seached during those 24 hours was tiny compared to the total range over which it wants to search:

Code:

Sun Nov 23 22:31:40 2008 
Sun Nov 23 22:31:40 2008 
Sun Nov 23 22:31:40 2008 Msieve v. 1.39
Sun Nov 23 22:31:40 2008 random seeds: 8ce70500 156790da
Sun Nov 23 22:31:40 2008 factoring 257373755693401357913719929886829557102394849008355700853322683429159360204157495062740626334976557033739235204025432832861137197259731899771993528783 (150 digits)
Sun Nov 23 22:31:41 2008 searching for 15-digit factors
Sun Nov 23 22:31:42 2008 commencing number field sieve (150-digit input)
Sun Nov 23 22:31:43 2008 commencing number field sieve polynomial selection
Sun Nov 23 22:31:43 2008 time limit set to 193.75 hours
Sun Nov 23 22:31:43 2008 searching leading coefficients from 752845 to 1181920

Compared to the actual leading coefficient seached range of 752845 to ~763980. At the clip it was going, it would cover about 21% of the default leading coefficient range in the default allotted time.

bsquared · 2008-11-26, 22:05

[offtopic]

If anyone's curious, I found the factors of this test C150 last week by GGNFS+Msieve:

Code:


Thu Nov 20 00:54:12 2008 prp68 factor: 63438322283542339334284542255681756793649517444922792176965979271553
Thu Nov 20 00:54:12 2008 prp82 factor: 4057070654281335716198698167114427911309196981049331216406050642992956912444248911

[/offtopic]

fivemack · 2008-11-27, 10:40

How exactly do you convert from the msieve score to the pol51 e-value? I have a database of pol51 e-values for about two hundred gnfs factorisations, and would like to be able to add msieve-determined polynomials to them on an equal footing.

Andi47 · 2008-11-27, 11:00

Quote:

Originally Posted by fivemack

How exactly do you convert from the msieve score to the pol51 e-value? I have a database of pol51 e-values for about two hundred gnfs factorisations, and would like to be able to add msieve-determined polynomials to them on an equal footing.

Quote:

Originally Posted by jasonp

PPS: Ben, the E scores between pol51 and msieve have different scaling. For a C150 the msieve score is expected to be smaller by a factor of 513, so the poly you found is already marginally better than the output of pol5

Does this mean, that the conversion factor between pol51* e and msieve e is not the same for diffenent input sizes (e.g. 120 or 150 digits)? In this case it would be nice if msieve additionally prints the pol51* e value to the output file.

jasonp · 2008-11-27, 16:58

The scaling factor is what divides the last entry in each row of the the table at the top of gnfs/poly/poly_skew.c, and yes it changes with the input size. For small sizes I just chose the scale factor so that the resulting scaled cutoff accepted all the same polynomials that were generated by pol51, then extrapolated the scaling factor to larger inputs.

Perhaps a better idea than estimating the equivalent pol51 score, is actually computing it. I wanted to avoid having to do that, because Murphy's E rating algorithm is much more computationally intensive than the rating system msieve uses now, but the current system actually is independent of the amount of translation and skew in the polynomial, so it may not be very accurate when both are large. It's an idea for 1.40

2008-11-25, 23:29	#45
jasonp Tribal Bullet Oct 2004 110111010101₂ Posts	The bounds on the norm used in the new poly selector are actually the same as in v1.38. One big difference is that the root sieve in v1.39 is much more powerful than in v1.38; if the mediocre polynomials that are popping out of the 1.39 run had been found in 1.38 they would have been discarded without being saved. The selection process uses the combined size and root scores when rating polynomials. Polynomials with small size are just as rare as before, but you're seeing more of them because the root sieve is producing excellent alpha values to compensate. A fair comparison would require porting the new root sieve code back into 1.38, maybe you'd start seeing exceptional polynomials pop out faster then. The only solution is to wait until you get good size and root properties simultaneously, and this is why poly selection takes so long. Getting lucky is the point of the exercise :) PS: I can't say for sure, but using a larger multiplier should not make a difference to polynomial quality at all. Modern poly selection works much better because choosing a leading rational coefficient larger than one gives you more possibilities than you can ever hope to search in a reasonable time, and using a sieve to find good alpha values improves the alpha much more than using a large multiplier ever could Last fiddled with by jasonp on 2008-11-25 at 23:33

2008-11-26, 20:13	#49
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 22405₈ Posts	x86_64 is on par with Win in beta2 I ran two side-by-side tests: a GNFS-119 and a GNFS-121. The integrator still fails (once; and indeed the candidate is then skipped), but the "expand failed" messages are gone. And the polynomials that were found by a Windows binary several days ago are being found by the x86_64. This bug is nailed. Thanks. So, if the integration fails to converge, then you would expect the polynomial be a dud, right? No need to fix that anytime soon, if so. I wonder how well the GNFS-119 will fare with beta2 on x86_64 (it was already faster than pol51's with beta1, but as we know now even that poly was not the best, most likely). I will re-run it.

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-26, 18:51	#48
jasonp Tribal Bullet Oct 2004 3,541 Posts	Right now you do get a printout of each coefficient range that has been searched; as long as that hasn't scrolled off your terminal window you can see the last range searched and set the next range manually.

2008-11-26, 21:42	#50
jasonp Tribal Bullet Oct 2004 3,541 Posts	If the integrator fails, you really cannot conclude anything about the polynomial. The integrand is dx / pow( (R(x)*A(x))^2, 1/6 ) where R(x) and A(x) are the rational and algebraic polynomials, respectively, and these have very large integer coefficients that cannot be stored to full accuracy in ordinary floating point. The integration interval is broken up into distinct regions with endpoints at the polynomial roots, and I think the problems arise because those roots are not computed to sufficient accuracy. The integrator samples the integrand extremely close to the endpoints, so it's possible that a polynomial value becomes exactly zero to the limit of roundoff error, which causes the infinities that you see. Frankly I'm surprised it doesn't fail more often than it does...

2008-11-27, 10:40	#53
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 7²×131 Posts	How exactly do you convert from the msieve score to the pol51 e-value? I have a database of pol51 e-values for about two hundred gnfs factorisations, and would like to be able to add msieve-determined polynomials to them on an equal footing.

2008-11-27, 16:58	#55
jasonp Tribal Bullet Oct 2004 3,541 Posts	The scaling factor is what divides the last entry in each row of the the table at the top of gnfs/poly/poly_skew.c, and yes it changes with the input size. For small sizes I just chose the scale factor so that the resulting scaled cutoff accepted all the same polynomials that were generated by pol51, then extrapolated the scaling factor to larger inputs. Perhaps a better idea than estimating the equivalent pol51 score, is actually computing it. I wanted to avoid having to do that, because Murphy's E rating algorithm is much more computationally intensive than the rating system msieve uses now, but the current system actually is independent of the amount of translation and skew in the polynomial, so it may not be very accurate when both are large. It's an idea for 1.40