Choosing the best polynomial - Page 7

jasonp · 2013-06-23, 22:56

The poly selection for RSA896 caught a bug in the CADO code for calculating the E value, and the Msieve code was changed to match the E value calculated by the CADO tools. Basically Msieve assumed that rational polynomials have an alpha value of zero, when in fact they behave worse than random numbers in terms of root properties, so the E value now reflects a rational alpha of about +0.50

Batalov · 2013-06-23, 23:09

The old fit ("expecting the E value from x to > y") will have to be adjusted then. I'll have a look into that.

VBCurtis · 2013-06-24, 03:36

Today produced two good polys. but not good enough- 6.38 and 6.37. I just moved the coeff range up from 10M to 900M, and stage 1 produces almost double the hit-rate, even with the stage 1 norm tightened a bit (5e25 from 6e25). I'll let stage 1 run 24h on this range and then post my 3 best polys.

Is there any standard practice for messing with the stage2_norm flag while running npr? I'd like to try tweaks on that for my best few dozen nps hits from the week, see if a 6.5 is hiding somewhere in there.

The new 5th degree poly likely puts a 6th out of reach- but, one more day anyway.

wombatman · 2013-06-25, 13:21

Best 6th degree polynomial from higher coefficients--alpha is still good, but the score still isn't any better.

Code:

R0: -17521586540479451333749501192476670
R1: 391741746126213149
A0: 4161504566609087523368754567954371334209013981
A1: -4977062877396027075592341074091405368264
A2: -196112245463392189835134022412141680
A3: 30585987157617220045072690150
A4: 298602220140347616355899
A5: -3810613825973646
A6: 3005640
skew 1974744.31, size 1.037e-015, alpha -10.156, combined = 4.555e-016 rroots = 6

VBCurtis · 2013-06-26, 07:01

Two decent polys, no home runs:

Code:

  R0: -6773300647376368371204971035943100
  R1: 9147330742953349
  A0: 6196856451525563071543714962359747237299175261
  A1: -20567809402462902341999646371740229391788
  A2: -15530994268093817486298457192984045
  A3: 61671847465698167140547075785
  A4: 9413160686088017597744
  A5: -4012021064093717
  A6: 900690120
  skew 1493791.87, size 1.511e-015, alpha -9.778, combined = 6.410e-016 rroots = 4

Very small skew on that first one...

Code:

  R0: -14209355044789740248460068568119813
  R1: 129300161681482375
  A0: 259238529409979597044702044054542080025342548080
  A1: 136914424560921554402593920881567472030108
  A2: -25780376564231964927794926144102830
  A3: -6045972430189592322258007904
  A4: -110711749792146227441
  A5: -203988539659592
  A6: 10566504
  skew 6310888.46, size 1.492e-015, alpha -9.038, combined = 6.385e-016 rroots = 4

This ends my search.

Batalov · 2013-06-26, 08:37

These are quite nice given the limited time.
(RSA team, in comparison, spent several CPU years.)
Kudos!

wombatman · 2013-06-26, 19:58

Question about these polynomials. When I run -np1 polydegree=6, I get the following coefficient range:

Code:

searching leading coefficients from 1 to 3868340

Curtis's A6 is much larger than that upper bound. Why would I get a max (chosen by MSieve) coefficient so much less than his? And I just noticed the first poly has a leading coefficient of 900 million. Something's way off.

Quote:

Originally Posted by VBCurtis

Two decent polys, no home runs:

Code:

  R0: -6773300647376368371204971035943100
  R1: 9147330742953349
  A0: 6196856451525563071543714962359747237299175261
  A1: -20567809402462902341999646371740229391788
  A2: -15530994268093817486298457192984045
  A3: 61671847465698167140547075785
  A4: 9413160686088017597744
  A5: -4012021064093717
  A6: 900690120
  skew 1493791.87, size 1.511e-015, alpha -9.778, combined = 6.410e-016 rroots = 4

Very small skew on that first one...

Code:

  R0: -14209355044789740248460068568119813
  R1: 129300161681482375
  A0: 259238529409979597044702044054542080025342548080
  A1: 136914424560921554402593920881567472030108
  A2: -25780376564231964927794926144102830
  A3: -6045972430189592322258007904
  A4: -110711749792146227441
  A5: -203988539659592
  A6: 10566504
  skew 6310888.46, size 1.492e-015, alpha -9.038, combined = 6.385e-016 rroots = 4

This ends my search.

Batalov · 2013-06-26, 20:34

Quote:

Originally Posted by VBCurtis

Today produced two good polys. but not good enough- 6.38 and 6.37. I just moved the coeff range up from 10M to 900M, and stage 1 produces almost double the hit-rate, ....

Quote:

Originally Posted by wombatman

Question about these polynomials. When I run -np1 polydegree=6, I get the following coefficient range:

Code:

searching leading coefficients from 1 to 3868340

Curtis's A6 is much larger than that upper bound. Why would I get a max (chosen by MSieve) coefficient so much less than his? And I just noticed the first poly has a leading coefficient of 900 million. Something's way off.

As Curtis explained above, he was using something like
msieve ... -np1 "polydegree=6 min_coeff=10000000 max_coeff=..."
msieve ... -np1 "polydegree=6 min_coeff=900000000 max_coeff=..."

wombatman · 2013-06-26, 20:46

Well now I feel like a dumbass. I was assuming those were fairly rigid limits in terms of what was practical/useful to search. Thanks.

Along these lines, is there a good rule of thumb for picking leading coefficients? Or is it the sort of experience-based flying-by-seats-of-pants choice that makes things interesting?

VBCurtis · 2013-06-26, 21:02

Greg (frmky) has posted in many recent threads that a higher coeff reduces skew, without altering discernably the average quality of polynomials. I thought 1e6 was pretty big, but then noticed the 5th degree poly we targeted had coeff of something like 1e11; so after 3-4 days of searching from 1e6 to 20e6, I jumped to 900m-920m.

I learned that for a given stage 1 norm, higher coeffs produce a longer search per coeff (specifically, "specialq range" is bigger for higher coeffs), but fewer coeffs are searched per 1M. At 900M, I was able to reduce the stage 1 norm by 20% while still getting the same hit rate per time in np1. I didn't take enough data to compare the nps quality per unit of GPU time.

I wonder if msieve's default behavior should be altered to start at 1e{degree}.

The msieve defaults you cite gave msieve an alternative stopping point to time per coeff for searches that do not specify coeff ranges- such as calls from aliqueit, etc.

wombatman · 2013-06-26, 21:18

Good information, Curtis. I'm going to play around with coefficients and see how changing them affects results. Thanks!

2013-06-23, 22:56	#67
jasonp Tribal Bullet Oct 2004 3,541 Posts	The poly selection for RSA896 caught a bug in the CADO code for calculating the E value, and the Msieve code was changed to match the E value calculated by the CADO tools. Basically Msieve assumed that rational polynomials have an alpha value of zero, when in fact they behave worse than random numbers in terms of root properties, so the E value now reflects a rational alpha of about +0.50 Last fiddled with by jasonp on 2013-06-23 at 23:00

2013-06-26, 20:46	#75
wombatman I moo ablest echo power! May 2013 29·61 Posts	Well now I feel like a dumbass. I was assuming those were fairly rigid limits in terms of what was practical/useful to search. Thanks. Along these lines, is there a good rule of thumb for picking leading coefficients? Or is it the sort of experience-based flying-by-seats-of-pants choice that makes things interesting? Last fiddled with by wombatman on 2013-06-26 at 20:53

2013-06-26, 21:02	#76
VBCurtis "Curtis" Feb 2005 Riverside, CA 4,861 Posts	Greg (frmky) has posted in many recent threads that a higher coeff reduces skew, without altering discernably the average quality of polynomials. I thought 1e6 was pretty big, but then noticed the 5th degree poly we targeted had coeff of something like 1e11; so after 3-4 days of searching from 1e6 to 20e6, I jumped to 900m-920m. I learned that for a given stage 1 norm, higher coeffs produce a longer search per coeff (specifically, "specialq range" is bigger for higher coeffs), but fewer coeffs are searched per 1M. At 900M, I was able to reduce the stage 1 norm by 20% while still getting the same hit rate per time in np1. I didn't take enough data to compare the nps quality per unit of GPU time. I wonder if msieve's default behavior should be altered to start at 1e{degree}. The msieve defaults you cite gave msieve an alternative stopping point to time per coeff for searches that do not specify coeff ranges- such as calls from aliqueit, etc. Last fiddled with by VBCurtis on 2013-06-26 at 21:10

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
Help choosing motherboard please.	Flatlander	GPU Computing	4	2011-01-26 08:15
Choosing the best CPU for sieving	siew	Factoring	14	2010-02-27 10:07
MPQS: choosing a good polynomial	ThiloHarich	Factoring	4	2006-09-05 07:51
Choosing amount of memory	azhad	Software	2	2004-10-16 16:41

2013-06-23, 23:09	#68
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶×13 Posts	The old fit ("expecting the E value from x to > y") will have to be adjusted then. I'll have a look into that.

2013-06-24, 03:36	#69
VBCurtis "Curtis" Feb 2005 Riverside, CA 4,861 Posts	Today produced two good polys. but not good enough- 6.38 and 6.37. I just moved the coeff range up from 10M to 900M, and stage 1 produces almost double the hit-rate, even with the stage 1 norm tightened a bit (5e25 from 6e25). I'll let stage 1 run 24h on this range and then post my 3 best polys. Is there any standard practice for messing with the stage2_norm flag while running npr? I'd like to try tweaks on that for my best few dozen nps hits from the week, see if a 6.5 is hiding somewhere in there. The new 5th degree poly likely puts a 6th out of reach- but, one more day anyway.

2013-06-26, 08:37	#72
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶×13 Posts	These are quite nice given the limited time. (RSA team, in comparison, spent several CPU years.) Kudos!

2013-06-26, 21:18	#77
wombatman I moo ablest echo power! May 2013 11011101001₂ Posts	Good information, Curtis. I'm going to play around with coefficients and see how changing them affects results. Thanks!