 mersenneforum.org Polynomial
 Register FAQ Search Today's Posts Mark Forums Read 2005-09-13, 14:38 #1 R.D. Silverman   Nov 2003 22×5×373 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-13, 21:44 #2 Zeta-Flux   May 2003 7×13×17 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-14, 01:18   #3
wblipp

"William"
May 2003
New Haven

23·5·59 Posts 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?  2005-09-14, 01:26 #4 trilliwig   Oct 2004 tropical Massachusetts 3·23 Posts factors as you say, but leaves a 24th degree polynomial expressible as a 12th degree in . You can then use the substitution 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 written as a sextic in .... Last fiddled with by trilliwig on 2005-09-14 at 01:29  2005-09-14, 14:55   #5
R.D. Silverman

Nov 2003

22·5·373 Posts Quote:
 Originally Posted by trilliwig factors as you say, but leaves a 24th degree polynomial expressible as a 12th degree in . You can then use the substitution 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 written as a sextic in ....

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  and 2^1 - 2^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.  2005-09-15, 06:46 #6 trilliwig   Oct 2004 tropical Massachusetts 3×23 Posts 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 , but it leaves a HUUGE constant coefficient , which is 186 digits, not much smaller than the SNFS difficulty at 191.5.  2005-09-16, 03:10 #7 wblipp   "William" May 2003 New Haven 44708 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 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.  2005-09-16, 11:24 #8 kubus   May 2003 Warsaw 2·7 Posts 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  2005-09-16, 12:28   #9
R.D. Silverman

Nov 2003

164448 Posts 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?  2005-09-16, 12:43   #10
R.D. Silverman

Nov 2003

22×5×373 Posts 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])  2005-09-16, 13:24   #11
kubus

May 2003
Warsaw

2·7 Posts 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). Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Miscellaneous Math 14 2017-02-18 19:46 jordis Msieve 22 2009-04-17 10:54 fivemack Factoring 61 2008-07-21 11:16 Kevin Puzzles 15 2007-09-25 17:22 buan Homework Help 3 2007-07-17 15:07

All times are UTC. The time now is 09:21.

Thu Jan 28 09:21:23 UTC 2021 up 56 days, 5:32, 0 users, load averages: 2.48, 2.46, 2.42