Polynomial selection

[CRGreathouse]

I'm trying to work out how to choose good SNFS polynomials and I thought I'd try to mine the collective wisdom here rather than re-invent the wheel. Feel free to share your own thoughts rather than answer my questions.

1. The ggnfs documentation suggests x^5 - 200 (SNFS difficulty 146.5) as superior to 4x^5 - 25 (SNFS difficulty 145.6). This suggests that having a monic polynomial is worth at least 0.9 SNFS difficulty. How far should you go to reduce the leading coefficient? And is going from 2x^5 to x^5 a bugger jump than 4x^5 to 2x^5, or are they the same? (Does being monic mean anything in particular, or is it just that you want to reduce the coefficient as far as reasonable?)

2. What is a good cutoff point for degree 4 and 5? How flexible is the boundary if you have a slightly better degree-k polynomial than a degree-(k±1) polynomial? Say you have a 100-digit number (quartic territory); how much better (in terms of SNFS difficulty) would a quintic need to be to induce a switch? 0.2? 3.0?

3. Is the 135% rule of thumb still approximately correct?

4. What programs are best at SNFS? Are there others I should try?

[henryzz]

Originally Posted by CRGreathouse

4. What programs are best at SNFS? Are there others I should try?

ggnfs with msieve postprocessing is what most people use currently
factmsieve.pl is the most common used script

[10metreh]

Originally Posted by CRGreathouse

I'm trying to work out how to choose good SNFS polynomials and I thought I'd try to mine the collective wisdom here rather than re-invent the wheel. Feel free to share your own thoughts rather than answer my questions.

1. The ggnfs documentation suggests x^5 - 200 (SNFS difficulty 146.5) as superior to 4x^5 - 25 (SNFS difficulty 145.6). This suggests that having a monic polynomial is worth at least 0.9 SNFS difficulty. How far should you go to reduce the leading coefficient? And is going from 2x^5 to x^5 a bugger jump than 4x^5 to 2x^5, or are they the same? (Does being monic mean anything in particular, or is it just that you want to reduce the coefficient as far as reasonable?)

That surprises me. If anything, I'd have thought 4x^5 - 25 with a lower difficulty was superior.

2. What is a good cutoff point for degree 4 and 5? How flexible is the boundary if you have a slightly better degree-k polynomial than a degree-(k±1) polynomial? Say you have a 100-digit number (quartic territory); how much better (in terms of SNFS difficulty) would a quintic need to be to induce a switch? 0.2? 3.0?

115-120 digits is a rough cutoff for degree 4-5, and test-sieve a small range (say 10k Q) to see which is faster. With difficulty 100, the quartics should be slightly faster than the quintics, but if the quintic is nicer it might be faster. Sometimes you just can't make a quartic for an S100 without increasing the difficulty by 10 or more. In this case, the quintic will probably be faster, or even the sextic (if there is one).

3. Is the 135% rule of thumb still approximately correct?

Depends on the size. The ratio seems to increase with the size. However, you cannot compare SNFS polynomials easily, and some numbers that do have a poly do not have as good a poly as others with a similar difficulty. So the answer is "It depends on the size and the number". Still, it is roughly correct for lower SNFSs.

4. What programs are best at SNFS? Are there others I should try?

I agree with henryzz. Feel free to post in the "Running GGNFS" thread.