Choosing the best polynomial - Page 2

wombatman · 2013-06-17, 04:05

Super. That's what I figured, but I wanted to make sure!

Batalov · 2013-06-17, 07:03

I wrote that hack (after fitting a bunch of historical data), and I will be the first to admit that at the 5th degree - 6th degree breakeven point (which is where c210 is), that formula is a complete ~~fiction~~ extrapolation (with no supporting points). Furthermore, the E values for the 5th and 6th degree are somewhat stitched together by Jason (with the help of a fudge factor) and are not directly comparable; instead, a careful simulated sieving experimant is needed to make the final call between a pair of the 5th- and 6th-degree polys.

Ask Greg "frmky" Childers what degrees he is planning on using for his upcoming gnfs-207 and gnfs-212 jobs. c207 is already in sieving; it is easy to find out the poly -- by joining the project and examining the workunit files. (doing it now... Ok. c207 is being done with 5th degree, norm 2.207127e-20 alpha -8.056539 e 1.558e-15 . Hope that this is not a secret ;-) at least a thousand NFS @ Home sieving participants know it.)

frmky · 2013-06-17, 22:23

No, I'm not that bad at keeping a secret!

C201
# norm 9.026462e-20 alpha -8.353613 e 3.808e-15 rroots 3

C207
# norm 2.207127e-20 alpha -8.056539 e 1.558e-15 rroots 5

C212
# norm 5.079440e-21 alpha -8.178263 e 5.467e-16 rroots 3

Edit: These are all degree 5, msieve's default. I didn't try searching for a degree 6. Also, I note that each of these is a bit below Serge's minimum extrapolation.

Batalov · 2013-06-18, 00:12

This is not necessarily a bad thing, because we don't know how good the extrapolation is in that range. At least the values are consistent! ;-)

You haven't started the c212, right? Is there still time (a few weeks?) to make a bid with a sextic (by the forumites! not by me)?

wombatman · 2013-06-18, 01:26

Good deal! I'm playing around with RSA210 searching with polydegree=6. I'm still in step 1 (up to ~8000 as a leading coefficient in ~1 day with a 400 MB file using a GTX 570 and 10 threads).

For what it's worth, msieve suggests the following by default:

Code:

max stage 1 norm: 2.72e+027
max stage 2 norm: 4.08e+026
min E-value: 6.00e-019

Thanks again for the additional information. It's awesome to learn so much about what's going on.

Batalov · 2013-06-18, 18:34

I flipped through old records and realized that the last time we raced 5th -vs- 6th degree was for the Bern(200) c204. 6th degree was within breathing distance. I suspect that for the c210 and c212, 6th degree may be actually better.

Is anyone interested to throw some Tesla/Fermi/GTX570+ computrons on the c212 6th degree poly selection?

P.S. The RSA-704 c212 was done with CADO-NFS with a degree 6 gnfs poly.

Batalov · 2013-06-18, 18:45

Quote:

Originally Posted by wombatman

Good deal! I'm playing around with RSA210 searching with polydegree=6. I'm still in step 1 (up to ~8000 as a leading coefficient in ~1 day with a 400 MB file using a GTX 570 and 10 threads).

Some people reported that low leading coefficients (e.g. 1-10000) take a long time to search and return fewer hits per time spent than some reasonably offset starting values, e.g. with ~2e4 (...or ~2e5 for 6th degree maybe?).

This is based on old tests, not on science, and could be wrong, - but shouldn't be harmful to test.

VBCurtis · 2013-06-18, 20:29

Quote:

Originally Posted by Batalov

I flipped through old records and realized that the last time we raced 5th -vs- 6th degree was for the Bern(200) c204. 6th degree was within breathing distance. I suspect that for the c210 and c212, 6th degree may be actually better.

Is anyone interested to throw some Tesla/Fermi/GTX570+ computrons on the c212 6th degree poly selection?

P.S. The RSA-704 c212 was done with CADO-NFS with a degree 6 gnfs poly.

I have a slow CUDA setup and wouldn't mind trying for a couple days for a degree 6. Where can I find the c212 candidate? Wombatman, this might be a good chance for you to search also, and then test-sieve; you'll get an educational taste of each step in the process, whilst also possibly contributing to NFS@home.

Edit: Is there any extrapolation possible from a small-scale search? I mean, if I find a poly in 72 hrs that performs within x% of Greg's degree 5, there is a value for x that would suggest we mount a full-scale deg 6 search for the c212, right?

Batalov · 2013-06-18, 20:37

The c212 is the cofactor of 10^770+1 - here. It could be fun to improve on Greg's polynomial, whose parameters are listed above: e 5.467e-16 but don't try to compare it to the 6th degree directly by value. Let's just try to get the best possible 6th degree poly: between them, they can be roughly compared by e value, but let's try to get several top contenders.

The c210 that OP is working on is one of the RSAs, I think?

frmky · 2013-06-18, 21:03

Sieving will start in just over 1 week from now. Here's the poly to beat:

Code:

# norm 5.079440e-21 alpha -8.178263 e 5.467e-16 rroots 3
skew: 136255886.66
c0: -210094660617235158281167281704470116399745308858195
c1: -5842228122167264862994127665572361751647881
c2: 78251666050988046826383875909123732
c3: 722037651605897444552776163
c4: -3262149587172057175
c5: 10092433680
Y0: -24382392754967924964120573553565948210138
Y1: 559803788355463651

wombatman · 2013-06-19, 00:22

Quote:

Originally Posted by Batalov

The c212 is the cofactor of 10^770+1 - here. It could be fun to improve on Greg's polynomial, whose parameters are listed above: e 5.467e-16 but don't try to compare it to the 6th degree directly by value. Let's just try to get the best possible 6th degree poly: between them, they can be roughly compared by e value, but let's try to get several top contenders.

The c210 that OP is working on is one of the RSAs, I think?

You are correct--I just went with one of the ones that hadn't (at least, not that I can find) been factored yet. And I think you're right about the low coefficients not being very useful. I'm thinking I'll move up to higher coefficients starting tonight.

I would also be interested in doing some polynomial searching for 6th degree. I have a GTX 570 that can run pretty much uninterrupted.

Edit: Also, I'm noticing in trying to run the polynomial selection step with '-nps' that I'm getting "expand failed" for every result. That seems a bit unusual, given that I've got ~700MB worth of potential starting factors. Any ideas what might be wrong?

2013-06-17, 22:23	#14
frmky Jul 2003 So Cal 2·3⁴·13 Posts	No, I'm not that bad at keeping a secret! C201 # norm 9.026462e-20 alpha -8.353613 e 3.808e-15 rroots 3 C207 # norm 2.207127e-20 alpha -8.056539 e 1.558e-15 rroots 5 C212 # norm 5.079440e-21 alpha -8.178263 e 5.467e-16 rroots 3 Edit: These are all degree 5, msieve's default. I didn't try searching for a degree 6. Also, I note that each of these is a bit below Serge's minimum extrapolation. Last fiddled with by frmky on 2013-06-17 at 22:34

2013-06-18, 01:26	#16
wombatman I moo ablest echo power! May 2013 6E9₁₆ Posts	Good deal! I'm playing around with RSA210 searching with polydegree=6. I'm still in step 1 (up to ~8000 as a leading coefficient in ~1 day with a 400 MB file using a GTX 570 and 10 threads). For what it's worth, msieve suggests the following by default: Code: max stage 1 norm: 2.72e+027 max stage 2 norm: 4.08e+026 min E-value: 6.00e-019 Thanks again for the additional information. It's awesome to learn so much about what's going on.

2013-06-18, 18:34	#17
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 9477₁₀ Posts	I flipped through old records and realized that the last time we raced 5th -vs- 6th degree was for the Bern(200) c204. 6th degree was within breathing distance. I suspect that for the c210 and c212, 6th degree may be actually better. Is anyone interested to throw some Tesla/Fermi/GTX570+ computrons on the c212 6th degree poly selection? P.S. The RSA-704 c212 was done with CADO-NFS with a degree 6 gnfs poly. Last fiddled with by Batalov on 2013-06-18 at 18:56 Reason: P.S.

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-17, 04:05	#12
wombatman I moo ablest echo power! May 2013 11011101001₂ Posts	Super. That's what I figured, but I wanted to make sure!

2013-06-17, 07:03	#13
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶·13 Posts	I wrote that hack (after fitting a bunch of historical data), and I will be the first to admit that at the 5th degree - 6th degree breakeven point (which is where c210 is), that formula is a complete ~~fiction~~ extrapolation (with no supporting points). Furthermore, the E values for the 5th and 6th degree are somewhat stitched together by Jason (with the help of a fudge factor) and are not directly comparable; instead, a careful simulated sieving experimant is needed to make the final call between a pair of the 5th- and 6th-degree polys. Ask Greg "frmky" Childers what degrees he is planning on using for his upcoming gnfs-207 and gnfs-212 jobs. c207 is already in sieving; it is easy to find out the poly -- by joining the project and examining the workunit files. (doing it now... Ok. c207 is being done with 5th degree, norm 2.207127e-20 alpha -8.056539 e 1.558e-15 . Hope that this is not a secret ;-) at least a thousand NFS @ Home sieving participants know it.)

2013-06-18, 00:12	#15
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶·13 Posts	This is not necessarily a bad thing, because we don't know how good the extrapolation is in that range. At least the values are consistent! ;-) You haven't started the c212, right? Is there still time (a few weeks?) to make a bid with a sextic (by the forumites! not by me)?

2013-06-18, 20:37	#20
Batalov "Serge" Mar 2008 Phi(4,2^7658614+1)/2 3⁶·13 Posts	The c212 is the cofactor of 10^770+1 - here. It could be fun to improve on Greg's polynomial, whose parameters are listed above: e 5.467e-16 but don't try to compare it to the 6th degree directly by value. Let's just try to get the best possible 6th degree poly: between them, they can be roughly compared by e value, but let's try to get several top contenders. The c210 that OP is working on is one of the RSAs, I think?