Concocting an SNFS polynomial for 2^2376-1

fivemack · 2007-07-05, 11:11

This is for M(2376) from the ElevenSmooth project.

The largest-degree algebraic factor of x^2376-1 is the largest-degree algebraic factor of x^1188+1, namely

F = x^720 + x^684 - x^612 - x^576 + x^504 + x^468 - x^396 - x^360 - x^324 + x^252 + x^216 - x^144 - x^108 + x^36 + 1

This is obviously symmetric, so, using the standard trick and putting z=x^36+z^-36, we have

F = x^360 * (z^10+z^9-10*z^8-10*z^7+34*z^6+34*z^5-43*z^4-43*z^3+12*z^2+12*z+1)

There's a lot of pattern to those coefficients; with y=z^2 we have

F = x^360 * ((z+1) * (y^5 - 10y^4 + 34y^3 - 43y^2 + 12y) + 1)

F(2) is a 217-digit number, so obviously completely impervious to GNFS with even unreasonable resources; it has a couple of small prime factors and a C195, which is merely totally impervious to GNFS with reasonable resources. I wonder if there's any way of using the quintic; or does the '+1' at the end have to translate into a correction term large enough to make the polynomial no longer special?

frmky · 2007-07-05, 16:23

$x^{792} - x^{396} + 1$ makes a great 6th order poly, and is doable with a difficulty of a C239. I don't see anything good that's smaller.

Greg

R.D. Silverman · 2007-07-09, 15:09

Quote:

Originally Posted by frmky

$x^{792} - x^{396} + 1$ makes a great 6th order poly, and is doable with a difficulty of a C239. I don't see anything good that's smaller.

Greg

There isn't anything better.

2007-07-05, 11:11	#1
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 7²·131 Posts	Concocting an SNFS polynomial for 2^2376-1 This is for M(2376) from the ElevenSmooth project. The largest-degree algebraic factor of x^2376-1 is the largest-degree algebraic factor of x^1188+1, namely F = x^720 + x^684 - x^612 - x^576 + x^504 + x^468 - x^396 - x^360 - x^324 + x^252 + x^216 - x^144 - x^108 + x^36 + 1 This is obviously symmetric, so, using the standard trick and putting z=x^36+z^-36, we have F = x^360 * (z^10+z^9-10z^8-10z^7+34z^6+34z^5-43z^4-43z^3+12z^2+12z+1) There's a lot of pattern to those coefficients; with y=z^2 we have F = x^360 * ((z+1) * (y^5 - 10y^4 + 34y^3 - 43y^2 + 12y) + 1) F(2) is a 217-digit number, so obviously completely impervious to GNFS with even unreasonable resources; it has a couple of small prime factors and a C195, which is merely totally impervious to GNFS with reasonable resources. I wonder if there's any way of using the quintic; or does the '+1' at the end have to translate into a correction term large enough to make the polynomial no longer special?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
SNFS Polynomial selection help?	mhill12	Factoring	59	2013-09-09 22:40
SNFS polynomial with very low yield	ryanp	Factoring	9	2013-04-03 06:33
SNFS Polynomial for 919^87-1	wblipp	Factoring	6	2011-08-23 04:59
How To Evaluate SNFS Polynomial Tricks?	wblipp	Factoring	4	2011-04-15 16:22
SNFS Polynomial	R.D. Silverman	NFSNET Discussion	4	2007-04-11 20:39

2007-07-05, 16:23	#2
frmky Jul 2003 So Cal 2106₁₀ Posts	$x^{792} - x^{396} + 1$ makes a great 6th order poly, and is doable with a difficulty of a C239. I don't see anything good that's smaller. Greg