mersenneforum.org GNFS polynomial degree
 Register FAQ Search Today's Posts Mark Forums Read

 2008-09-26, 17:26 #1 joral     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?
 2008-09-26, 17:49 #2 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 22×3×7×109 Posts 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).
 2008-09-26, 18:08 #3 joral     Mar 2008 5510 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?
2008-09-26, 18:41   #4
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

3·43·79 Posts

Quote:
 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

2008-09-26, 21:25   #5
fivemack
(loop (#_fork))

Feb 2006
Cambridge, England

632310 Posts

Quote:
 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.

 2008-09-26, 22:02 #6 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 23C416 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...)
2008-09-26, 22:15   #7
jasonp
Tribal Bullet

Oct 2004

3·1,163 Posts

Quote:
 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.

Last fiddled with by jasonp on 2008-09-26 at 22:21

 Similar Threads Thread Thread Starter Forum Replies Last Post lavalamp Factoring 15 2018-02-11 14:46 carpetpool Miscellaneous Math 14 2017-02-18 19:46 Unregistered Information & Answers 3 2011-04-16 14:24 fivemack Factoring 20 2007-12-26 10:36 JHansen Factoring 0 2004-11-07 12:15

All times are UTC. The time now is 05:33.

Wed Nov 25 05:33:54 UTC 2020 up 76 days, 2:44, 4 users, load averages: 1.69, 1.63, 1.70