mersenneforum.org  

Go Back   mersenneforum.org > Other Stuff > Archived Projects > NFSNET Discussion

 
 
Thread Tools
Old 2005-09-13, 14:38   #1
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Question 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.
R.D. Silverman is offline  
Old 2005-09-13, 21:44   #2
Zeta-Flux
 
Zeta-Flux's Avatar
 
May 2003

2·761 Posts
Default

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
Zeta-Flux is offline  
Old 2005-09-14, 01:18   #3
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22·32·5·13 Posts
Default

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?
wblipp is offline  
Old 2005-09-14, 01:26   #4
trilliwig
 
trilliwig's Avatar
 
Oct 2004
tropical Massachusetts

3×23 Posts
Default

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
trilliwig is offline  
Old 2005-09-14, 14:55   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

161008 Posts
Thumbs up

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.
R.D. Silverman is offline  
Old 2005-09-15, 06:46   #6
trilliwig
 
trilliwig's Avatar
 
Oct 2004
tropical Massachusetts

4516 Posts
Default

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.
trilliwig is offline  
Old 2005-09-16, 03:10   #7
wblipp
 
wblipp's Avatar
 
"William"
May 2003
New Haven

22×32×5×13 Posts
Default

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 2689 + 2345 + 1

I understand that this is x13 + 227x6 + 1
where x=253

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*x12+2ax11+(4a+1)x10+(3a+1)x9+a*x8+2ax7
+(4a+26843547)x6
+ax5+2ax4+(4a+1)x3+(3a+1)x2+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*x12+2ax11+4ax10+8ax9+16a*x8+32ax7
+(64a+16642)x6
+abx5+2abx4+4abx3+8abx2+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.
wblipp is offline  
Old 2005-09-16, 11:24   #8
kubus
 
kubus's Avatar
 
May 2003
Warsaw

2×7 Posts
Default

Here are my calculations.

We can represent 2,1378M as y13+xy6+1,
where y=253 and x=227.

2,26L is y-x+1.

Now dividing y13+xy6+1 by y-x+1 and taking advantage of an equality x2=2y we get
A(y)+xB(y), where
A(y)=y12+y11-y10-y9+y8+y7-y6+y5+y4-y3-y2+y+1
B(y)=y11-y9+y7+y4-y2+1

A(y) and B(y) are symmetrical so we reduce the coeffs by representing poly with root z=227+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
kubus is offline  
Old 2005-09-16, 12:28   #9
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

11100010000002 Posts
Default

Quote:
Originally Posted by kubus
Here are my calculations.

We can represent 2,1378M as y13+xy6+1,
where y=253 and x=227.

2,26L is y-x+1.

Now dividing y13+xy6+1 by y-x+1 and taking advantage of an equality x2=2y we get
A(y)+xB(y), where
A(y)=y12+y11-y10-y9+y8+y7-y6+y5+y4-y3-y2+y+1
B(y)=y11-y9+y7+y4-y2+1

A(y) and B(y) are symmetrical so we reduce the coeffs by representing poly with root z=227+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 is offline  
Old 2005-09-16, 12:43   #10
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

26×113 Posts
Default

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])
R.D. Silverman is offline  
Old 2005-09-16, 13:24   #11
kubus
 
kubus's Avatar
 
May 2003
Warsaw

2×7 Posts
Default

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 k6=-64 if we want a sextic in (z + k/z).
kubus is offline  
 

Thread Tools


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

All times are UTC. The time now is 01:55.

Mon Nov 30 01:55:28 UTC 2020 up 80 days, 23:06, 3 users, load averages: 1.33, 1.20, 1.18

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.