mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2008-09-26, 17:26   #1
joral
 
joral's Avatar
 
Mar 2008

5·11 Posts
Default 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?
joral is offline   Reply With Quote
Old 2008-09-26, 17:49   #2
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

22×3×7×109 Posts
Default

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).
Batalov is offline   Reply With Quote
Old 2008-09-26, 18:08   #3
joral
 
joral's Avatar
 
Mar 2008

5510 Posts
Default

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?
joral is offline   Reply With Quote
Old 2008-09-26, 18:41   #4
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

3·43·79 Posts
Default

Quote:
Originally Posted by joral View Post
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
xilman is offline   Reply With Quote
Old 2008-09-26, 21:25   #5
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

632310 Posts
Default

Quote:
Originally Posted by xilman View Post
|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.
fivemack is offline   Reply With Quote
Old 2008-09-26, 22:02   #6
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

23C416 Posts
Default

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...)
Batalov is offline   Reply With Quote
Old 2008-09-26, 22:15   #7
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3·1,163 Posts
Default

Quote:
Originally Posted by Batalov View Post
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
jasonp is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Choice of SNFS polynomial degree lavalamp Factoring 15 2018-02-11 14:46
Polynomial Discriminant is n^k for an n-1 degree polynomial carpetpool Miscellaneous Math 14 2017-02-18 19:46
GNFS polynomial selection Unregistered Information & Answers 3 2011-04-16 14:24
6^383+1 by GNFS (polynomial search; now complete) fivemack Factoring 20 2007-12-26 10:36
GNFS polynomial search tools 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.