GNFS polynomial degree

[joral]

Hi guys,

For GNFS polynomial selection, at which number sizes would it be better to drop back to a degree 4, or go up to a degree 6 polynomial?

[Batalov]

The answer (general guidelines) is in the def-par.txt file -- see the numbers 4 and 5. E.g. here - http://ggnfs.svn.sourceforge.net/vie...in/def-par.txt

Fifth degree polynomials are good in a wide interval from SNFS complexity 120 to 200-210. Around SNFS complexity 120-130 - transition from 4 to 5, under 96 digits use MPQS. Around 200 - transition from 5 to 6 (it depends; either may be good). Over 250 digits - transition from 6 to 7 (maybe).

For GNFS, there's degrees 4 and 5. (as a rule of thumb 4 under 98 digits; but then again - you may use MPQS there).

[joral]

I was more interested in the GNFS side of it... So degree 4 is more in the MPQS range. I assume degree 6 is outside the current normal GNFS range?

[xilman]

Originally Posted by joral

I was more interested in the GNFS side of it... So degree 4 is more in the MPQS range. I assume degree 6 is outside the current normal GNFS range?

|Correct.

Degree 5 appears to be sufficient up to 200 digits / 650 bits. It was what was used for RSA200 for example.

Paul

[fivemack]

Originally Posted by xilman

|Correct.

Degree 5 appears to be sufficient up to 200 digits / 650 bits. It was what was used for RSA200 for example.

Paul

Is it certain that this is 'appears to be sufficient' or just 'has extremely well-optimised code written for polynomial generation'? A quick search for 'RSA768 polynomial' gives a paper containing degree-5 one at even that size, which is well into the sextics-are-better range for SNFS.

[Batalov]

We may really need a pol61 version soon. But it's hard.

I wonder if a naive pol61 could be hacked together with a vanishing fourth or third (probably not fifth) term? (so that optimization wouldn't go nowhere because of too big a search space; trying to leave the search space the same by a vanishing fixed term...)

[jasonp]

Originally Posted by Batalov

We may really need a pol61 version soon. But it's hard.

I wonder if a naive pol61 could be hacked together with a vanishing fourth or third (probably not fifth) term? (so that optimization wouldn't go nowhere because of too big a search space; trying to leave the search space the same by a vanishing fixed term...)

pol61opt would be pretty easy; pol61m0b would be much harder. It's another item on the to-do list.

The current code picks the X^5 coefficient, builds a class of polynomials where the X^4 coefficient is quaranteed to be small, searches for polynomials within that class for a polynomial where the X^3 coefficient is small, and then tries to tweak the skew and translate the coefficients so that the X^2 coefficient is small. For a 6th-degree poly, add 1 to all those exponents and look for small X^2 and X^3 coefficients after tweaking. The trouble is in all the hardwired-to-degree-5 code that we have to work with.