20080926, 17:26  #1 
Mar 2008
5·11 Posts 
GNFS polynomial degree
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? 
20080926, 17:49  #2 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
2^{2}×3×7×109 Posts 
The answer (general guidelines) is in the defpar.txt file  see the numbers 4 and 5. E.g. here  http://ggnfs.svn.sourceforge.net/vie...in/defpar.txt
Fifth degree polynomials are good in a wide interval from SNFS complexity 120 to 200210. Around SNFS complexity 120130  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). 
20080926, 18:08  #3 
Mar 2008
55_{10} Posts 
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?

20080926, 18:41  #4  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
3·43·79 Posts 
Quote:
Degree 5 appears to be sufficient up to 200 digits / 650 bits. It was what was used for RSA200 for example. Paul 

20080926, 21:25  #5 
(loop (#_fork))
Feb 2006
Cambridge, England
6323_{10} Posts 
Is it certain that this is 'appears to be sufficient' or just 'has extremely welloptimised code written for polynomial generation'? A quick search for 'RSA768 polynomial' gives a paper containing degree5 one at even that size, which is well into the sexticsarebetter range for SNFS.

20080926, 22:02  #6 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2
23C4_{16} Posts 
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...) 
20080926, 22:15  #7  
Tribal Bullet
Oct 2004
3·1,163 Posts 
Quote:
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 6thdegree 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 hardwiredtodegree5 code that we have to work with. Last fiddled with by jasonp on 20080926 at 22:21 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Choice of SNFS polynomial degree  lavalamp  Factoring  15  20180211 14:46 
Polynomial Discriminant is n^k for an n1 degree polynomial  carpetpool  Miscellaneous Math  14  20170218 19:46 
GNFS polynomial selection  Unregistered  Information & Answers  3  20110416 14:24 
6^383+1 by GNFS (polynomial search; now complete)  fivemack  Factoring  20  20071226 10:36 
GNFS polynomial search tools  JHansen  Factoring  0  20041107 12:15 