Polynomial

R.D. Silverman · 2005-09-13, 14:38

I am currently working on the 2L,M numbers. I have finished sieving
2,1322M and am nearly done (another 2 days) with 2,1334L. 2,1346L
is queued. 2,1366L and 2,1366M will then follow.

I am seeking a good polynomial for 2,1378M. 2^1378+1 = x^26 + 1
with x = 2^53. This polynomial can be factored into a quadratic and
two 12'th degree polynomials in 2^53. I expect that the 12'th degree
polynomials can then be expressed as a sextic in (x + 1/x) or perhaps
(x + 2/x). Doing this without computer algebra software is tedious and
error prone.

The polynomial might better be expressed as x^(26k) + 1 where k is odd,
yielding x^(52n+26) + 1. This will factor into a quadratic [in x^2n] and
two 12'th degree polynomials [also in x^2n].

Might someone compute the coefficients for me? It is messy to do by hand.

Zeta-Flux · 2005-09-13, 21:44

Plugging these into Mathematica I get:

x^26 + 1 = (1 + x^2) (1 - x^2 + x^4 - x^6 + x^8 - x^10 + x^12 - x^14 + x^16 - x^18 + x^20 - x^22 + x^24)

and

x^(52 n + 26) + 1 =(1 + x^(2 + 4 n)) (1 - x^(2 + 4 n) + x^(4 + 8 n) - x^(6 + 12 n) + x^(8 + 16 n) - x^(10 + 20 n) + x^(12 + 24 n) - x^(14 + 28 n) + x^(16 + 32 n) - x^(18 + 36 n) + x^(20 + 40 n) - x^(22 + 44 n) + x^(24 + 48 n))

For specific values of n, the second polynomial factors further. But in general these aren't very good factorizations. In fact, for n=6, the bigger factor doesn't factor further. And in general the smaller factor always has a factor of (1+x^2) and one other factor.

Are you sure these are the right polynomials? Don't you need to pull a 4 out front or something?

Best,
Pace

wblipp · 2005-09-14, 01:18

Quote:

Originally Posted by R.D. Silverman

I am seeking a good polynomial for 2,1378M.

How about 32x^6 + 8x^3 + 1
with x=2^114?

trilliwig · 2005-09-14, 01:26

$X^{26}-1$ factors as you say, but $X^{26}+1$ leaves a 24th degree polynomial expressible as a 12th degree in $X^2$ . You can then use the substitution $Z = X^2 + X^{-2}$ to get it down to a 6th degree polynomial, but you probably don't want to use it as it has SNFS difficulty 383.

I can't see how to get anything better than the bog-standard $2^{690} + 2^{346} + 2$ written as a sextic in $2^{115}$ ....

R.D. Silverman · 2005-09-14, 14:55

Quote:

Originally Posted by trilliwig

$X^{26}-1$ factors as you say, but $X^{26}+1$ leaves a 24th degree polynomial expressible as a 12th degree in $X^2$ . You can then use the substitution $Z = X^2 + X^{-2}$ to get it down to a 6th degree polynomial, but you probably don't want to use it as it has SNFS difficulty 383.

I can't see how to get anything better than the bog-standard $2^{690} + 2^{346} + 2$ written as a sextic in $2^{115}$ ....

When x is a power of 2, x^26 + 1 has an Aurefeuillian factorization.

1378 is divisible by 13 and phi(13) = 12. 2^1378 + 1 = X*Y =
(2^689 + 2^345 + 1) * ( 2^689 - 2^345 + 1). Now, after pulling out
the algebraic factors 2^1 + 2^1 + 1 [5] and 2^1 - 2^1 + 1[1], the
X AND Y can be expressed as degree 12 polynomials in 2^53.

These in turn should have a representation as a SEXTIC in (2^53 + 2^-53)
or perhaps in (2^53 + 2^-52).

This works ONLY when x is a power of 2; it does not work for general x..
I am sorry that I did not make this clearer.

This allows us to take advantage of the algebraic factor 2^106 + 1 of
2^1378+1. As a result, instead of x^6 - 2x^3 + 2 with root 2^115,
we can get a sextic with root 2^53 + 2^-53. (norm ~ 2^106)
Thus, the root is quite a bit smaller. This makes the norms for the
linear polynomial smaller by a factor of 2^9.

Numbers of the form y^13 + 1 can be expressed as a sextic in (y+1/y).
Here, we can do even better. Because the base is 2, we also get an
Aurefeullian factorization.

However, grinding out the coefficients of the sextic is messy to do by hand.

trilliwig · 2005-09-15, 06:46

Hm, I can get close, but no cigar.

Code:

? Nfull=2^1378+1
? L=2^689-2^345+1
? M=2^689+2^345+1
? flist=factor(2^26*x^52+1)
%4 =
[2*x^2 - 2*x + 1 1]

[2*x^2 + 2*x + 1 1]

[4096*x^24 - 4096*x^23 + 2048*x^22 - 1024*x^20 + 1024*x^19 - 512*x^18 + 256*x^16 - 256*x^15 + 128*x^14 - 64*x^12 + 32*x^10 - 32*x^9 + 16*x^8 - 8*x^6 + 8*x^5 - 4*x^4 + 2*x^2 - 2*x + 1 1]

[4096*x^24 + 4096*x^23 + 2048*x^22 - 1024*x^20 - 1024*x^19 - 512*x^18 + 256*x^16 + 256*x^15 + 128*x^14 - 64*x^12 + 32*x^10 + 32*x^9 + 16*x^8 - 8*x^6 - 8*x^5 - 4*x^4 + 2*x^2 + 2*x + 1 1]

? P=flist[4,1]
%5 = 4096*x^24 + 4096*x^23 + 2048*x^22 - 1024*x^20 - 1024*x^19 - 512*x^18 + 256*x^16 + 256*x^15 + 128*x^14 - 64*x^12 + 32*x^10 + 32*x^9 + 16*x^8 - 8*x^6 - 8*x^5 - 4*x^4 + 2*x^2 + 2*x + 1

? Mprim=subst(P,x,2^26)
%6 = 285152542850491175357501403430350705193444129732329634402348763225297093979008916513412511048984163942486513060254213059514241871206854248405437313525494851669503299027787512159802595435610113

? z=2*x+1/x
%7 = (2*x^2 + 1)/x

? P/x^12-eval(Pol([1,2,-22,-44,172,344,-560,-1120,672,1344,-224,-448,-64],'z))
%8 = 0

? Q=Pol([1,2,-22,-44,172,344,-560,-1120,672,1344,-224,-448,-64],'z)
%9 = z^12 + 2*z^11 - 22*z^10 - 44*z^9 + 172*z^8 + 344*z^7 - 560*z^6 - 1120*z^5 + 672*z^4 + 1344*z^3 - 224*z^2 - 448*z - 64

? xmod=Mod(2^26,Mprim)
%10 = Mod(67108864, 285152542850491175357501403430350705193444129732329634402348763225297093979008916513412511048984163942486513060254213059514241871206854248405437313525494851669503299027787512159802595435610113)

? zmod=2*xmod+1/xmod
%11 = Mod(285152538601387169506781365053581230592433074122088195472170561991719913693300399990037647880200513410357643430058818003293158177788323557633287625439025178669303926415798445740983284907638783, 285152542850491175357501403430350705193444129732329634402348763225297093979008916513412511048984163942486513060254213059514241871206854248405437313525494851669503299027787512159802595435610113)

? subst(Q,'z,zmod)
%12 = Mod(0, 285152542850491175357501403430350705193444129732329634402348763225297093979008916513412511048984163942486513060254213059514241871206854248405437313525494851669503299027787512159802595435610113)

? z2mod=zmod^2
%13 = Mod(8498207948384856356148164994775234696058589277482298461713184792056933159713585920683296902912626823080244012032643423420301080480146077365260197802849412416499960801672859247332818950, 285152542850491175357501403430350705193444129732329634402348763225297093979008916513412511048984163942486513060254213059514241871206854248405437313525494851669503299027787512159802595435610113)

? neg_c0mod=64/(1+2/zmod)
%14 = Mod(271942652322184754529069161754860585240769190626965451171865847338390750856691737618601477021484144551752615924320273899334633409481993696363818114000495981271054974909227003705267585088, 285152542850491175357501403430350705193444129732329634402348763225297093979008916513412511048984163942486513060254213059514241871206854248405437313525494851669503299027787512159802595435610113)

? neg_c0=component(neg_c0mod,2)
%15 = 271942652322184754529069161754860585240769190626965451171865847338390750856691737618601477021484144551752615924320273899334633409481993696363818114000495981271054974909227003705267585088

? mpoly=Pol([1,-22,172,-560,672,-224,-neg_c0],zsquare)
%16 = zsquare^6 - 22*zsquare^5 + 172*zsquare^4 - 560*zsquare^3 + 672*zsquare^2 - 224*zsquare - 271942652322184754529069161754860585240769190626965451171865847338390750856691737618601477021484144551752615924320273899334633409481993696363818114000495981271054974909227003705267585088

? subst(mpoly,zsquare,z2mod)
%17 = Mod(0, 285152542850491175357501403430350705193444129732329634402348763225297093979008916513412511048984163942486513060254213059514241871206854248405437313525494851669503299027787512159802595435610113)

? log(neg_c0)/log(10)
%18 = 185.43447732901241625166315915028769913

? log(Mprim)/log(10)
%19 = 191.45507724876353223637684615191137519

P is a 24th degree polynomial so the degree-halving trick only gets us down to degree 12. There's still some relationships among the coefficients which allows us to get down to a sextic in $\displaystyle{\LARGE z^2 = \frac{2^{106}+2^{54}+1}{2^{52}}}$ ,
but it leaves a HUUGE constant coefficient $\LARGE\displaystyle{\frac{-64}{1+\frac{2}{z}}}$ , which is 186 digits, not much smaller than the SNFS difficulty at 191.5.

wblipp · 2005-09-16, 03:10

I tried to follow Bob's instructions as a learning experience. It all sounded clear before I started, but I soon had trouble figuring out what to do.

I understand that 2,1378M has factors of 2,104L, 2,26L, and 2,2M.

I understand that 2,1378M is 2⁶⁸⁹ + 2³⁴⁵ + 1

I understand that this is x¹³ + 2²⁷x⁶ + 1
where x=2⁵³

But I don't understand how to pull the 2,2M factor out and get a 12th degree polynomial in x.

The only thing I have thought of is to treat this as school boy long division with base 2^53. That gives

a*x¹²+2ax¹¹+(4a+1)x¹⁰+(3a+1)x⁹+a*x⁸+2ax⁷
+(4a+26843547)x⁶
+ax⁵+2ax⁴+(4a+1)x³+(3a+1)x²+ax+2a+1

a=1801439850948198

Since I don't understand what's going on, I tried dividing out the 2,26L by the same method. That gave
a*x¹²+2ax¹¹+4ax¹⁰+8ax⁹+16a*x⁸+32ax⁷
+(64a+16642)x⁶
+abx⁵+2abx⁴+4abx³+8abx²+16abx+32ab+1

a=1116825698046
b=126

I know how to turn a symmetric 12th degree polynomial in x into a 6th degree polynomial in (x + 1/x),
but that doesn't seem applicable here. Either I've got the wrong polynomials or there is a different trick.

kubus · 2005-09-16, 11:24

Here are my calculations.

We can represent 2,1378M as y¹³+xy⁶+1,
where y=2⁵³ and x=2²⁷.

2,26L is y-x+1.

Now dividing y¹³+xy⁶+1 by y-x+1 and taking advantage of an equality x²=2y we get
A(y)+xB(y), where
A(y)=y¹²+y¹¹-y¹⁰-y⁹+y⁸+y⁷-y⁶+y⁵+y⁴-y³-y²+y+1
B(y)=y¹¹-y⁹+y⁷+y⁴-y²+1

A(y) and B(y) are symmetrical so we reduce the coeffs by representing poly with root z=2²⁷+2^-26. We get 12th degree polynomial and in fact this is trilliwig's formula %9.

wblipp, I don't understand how to "pull out" 2,2M, too.

kubus

R.D. Silverman · 2005-09-16, 12:28

Quote:

Originally Posted by kubus

Here are my calculations.

We can represent 2,1378M as y¹³+xy⁶+1,
where y=2⁵³ and x=2²⁷.

2,26L is y-x+1.

Now dividing y¹³+xy⁶+1 by y-x+1 and taking advantage of an equality x²=2y we get
A(y)+xB(y), where
A(y)=y¹²+y¹¹-y¹⁰-y⁹+y⁸+y⁷-y⁶+y⁵+y⁴-y³-y²+y+1
B(y)=y¹¹-y⁹+y⁷+y⁴-y²+1

A(y) and B(y) are symmetrical so we reduce the coeffs by representing poly with root z=2²⁷+2^-26. We get 12th degree polynomial and in fact this is trilliwig's formula %9.

wblipp, I don't understand how to "pull out" 2,2M, too.

kubus

Yes, I was looking for formula %9. I was hoping that it might be
symmetric. It is not, but I thought that if it isn't, it might have a
representation as a sextic not in (z+1/z), but rather [with Z = 2^53]
in (z + 2/z). It seems that it does, but the constant is much too large.
Perhaps we might try a sextic in (z + k/z) for some other value of k?

R.D. Silverman · 2005-09-16, 12:43

Quote:

Originally Posted by R.D. Silverman

Yes, I was looking for formula %9. I was hoping that it might be
symmetric. It is not, but I thought that if it isn't, it might have a
representation as a sextic not in (z+1/z), but rather [with Z = 2^53]
in (z + 2/z). It seems that it does, but the constant is much too large.
Perhaps we might try a sextic in (z + k/z) for some other value of k?

I am not familiar with the syntax of Maple.

The above calculation should solve for (c1, c2, c3, .....) where

(z + 2/z)^6 + c1 (z + 2/z)^5 + c2 (z + 2/z)^4 + c3 (z + 2/z)^3 + .... =

z^-6 *(z^12 + 2z^11 - 22z^10 - 44z^9 ........ etc [expression %9])

kubus · 2005-09-16, 13:24

Quote:

Originally Posted by R.D. Silverman

Yes, I was looking for formula %9. I was hoping that it might be
symmetric. It is not, but I thought that if it isn't, it might have a
representation as a sextic not in (z+1/z), but rather [with Z = 2^53]
in (z + 2/z). It seems that it does, but the constant is much too large.
Perhaps we might try a sextic in (z + k/z) for some other value of k?

No way. Constant coeff in %9 is -64, so there must be k⁶=-64 if we want a sextic in (z + k/z).

2005-09-13, 14:38	#1
R.D. Silverman "Bob Silverman" Nov 2003 North of Boston 1110111010011₂ Posts	Polynomial I am currently working on the 2L,M numbers. I have finished sieving 2,1322M and am nearly done (another 2 days) with 2,1334L. 2,1346L is queued. 2,1366L and 2,1366M will then follow. I am seeking a good polynomial for 2,1378M. 2^1378+1 = x^26 + 1 with x = 2^53. This polynomial can be factored into a quadratic and two 12'th degree polynomials in 2^53. I expect that the 12'th degree polynomials can then be expressed as a sextic in (x + 1/x) or perhaps (x + 2/x). Doing this without computer algebra software is tedious and error prone. The polynomial might better be expressed as x^(26k) + 1 where k is odd, yielding x^(52n+26) + 1. This will factor into a quadratic [in x^2n] and two 12'th degree polynomials [also in x^2n]. Might someone compute the coefficients for me? It is messy to do by hand.

2005-09-14, 01:26	#4
trilliwig Oct 2004 tropical Massachusetts 3·23 Posts	$X^{26}-1$ factors as you say, but $X^{26}+1$ leaves a 24th degree polynomial expressible as a 12th degree in $X^2$ . You can then use the substitution $Z = X^2 + X^{-2}$ to get it down to a 6th degree polynomial, but you probably don't want to use it as it has SNFS difficulty 383. I can't see how to get anything better than the bog-standard $2^{690} + 2^{346} + 2$ written as a sextic in $2^{115}$ .... Last fiddled with by trilliwig on 2005-09-14 at 01:29

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Polynomial Discriminant is n^k for an n-1 degree polynomial	carpetpool	Miscellaneous Math	14	2017-02-18 19:46
How to use my own polynomial with Msieve	jordis	Msieve	22	2009-04-17 10:54
5^421-1 polynomial search	fivemack	Factoring	61	2008-07-21 11:16
Guess the Polynomial	Kevin	Puzzles	15	2007-09-25 17:22
[Need help] about Matrix Polynomial	buan	Homework Help	3	2007-07-17 15:07

2005-09-13, 21:44	#2
Zeta-Flux May 2003 60B₁₆ Posts	Plugging these into Mathematica I get: x^26 + 1 = (1 + x^2) (1 - x^2 + x^4 - x^6 + x^8 - x^10 + x^12 - x^14 + x^16 - x^18 + x^20 - x^22 + x^24) and x^(52 n + 26) + 1 =(1 + x^(2 + 4 n)) (1 - x^(2 + 4 n) + x^(4 + 8 n) - x^(6 + 12 n) + x^(8 + 16 n) - x^(10 + 20 n) + x^(12 + 24 n) - x^(14 + 28 n) + x^(16 + 32 n) - x^(18 + 36 n) + x^(20 + 40 n) - x^(22 + 44 n) + x^(24 + 48 n)) For specific values of n, the second polynomial factors further. But in general these aren't very good factorizations. In fact, for n=6, the bigger factor doesn't factor further. And in general the smaller factor always has a factor of (1+x^2) and one other factor. Are you sure these are the right polynomials? Don't you need to pull a 4 out front or something? Best, Pace

2005-09-16, 03:10	#7
wblipp "William" May 2003 Near Grandkid 2,377 Posts	I tried to follow Bob's instructions as a learning experience. It all sounded clear before I started, but I soon had trouble figuring out what to do. I understand that 2,1378M has factors of 2,104L, 2,26L, and 2,2M. I understand that 2,1378M is 2⁶⁸⁹ + 2³⁴⁵ + 1 I understand that this is x¹³ + 2²⁷x⁶ + 1 where x=2⁵³ But I don't understand how to pull the 2,2M factor out and get a 12th degree polynomial in x. The only thing I have thought of is to treat this as school boy long division with base 2^53. That gives ax¹²+2ax¹¹+(4a+1)x¹⁰+(3a+1)x⁹+ax⁸+2ax⁷ +(4a+26843547)x⁶ +ax⁵+2ax⁴+(4a+1)x³+(3a+1)x²+ax+2a+1 a=1801439850948198 Since I don't understand what's going on, I tried dividing out the 2,26L by the same method. That gave ax¹²+2ax¹¹+4ax¹⁰+8ax⁹+16ax⁸+32ax⁷ +(64a+16642)x⁶ +abx⁵+2abx⁴+4abx³+8abx²+16abx+32ab+1 a=1116825698046 b=126 I know how to turn a symmetric 12th degree polynomial in x into a 6th degree polynomial in (x + 1/x), but that doesn't seem applicable here. Either I've got the wrong polynomials or there is a different trick.

2005-09-16, 11:24	#8
kubus May 2003 Warsaw 3·5 Posts	Here are my calculations. We can represent 2,1378M as y¹³+xy⁶+1, where y=2⁵³ and x=2²⁷. 2,26L is y-x+1. Now dividing y¹³+xy⁶+1 by y-x+1 and taking advantage of an equality x²=2y we get A(y)+xB(y), where A(y)=y¹²+y¹¹-y¹⁰-y⁹+y⁸+y⁷-y⁶+y⁵+y⁴-y³-y²+y+1 B(y)=y¹¹-y⁹+y⁷+y⁴-y²+1 A(y) and B(y) are symmetrical so we reduce the coeffs by representing poly with root z=2²⁷+2^-26. We get 12th degree polynomial and in fact this is trilliwig's formula %9. wblipp, I don't understand how to "pull out" 2,2M, too. kubus