20050913, 14:38  #1 
"Bob Silverman"
Nov 2003
North of Boston
2^{3}·937 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. 
20050913, 21:44  #2 
May 2003
3013_{8} 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 
20050914, 01:18  #3  
"William"
May 2003
New Haven
3·7·113 Posts 
Quote:
with x=2^114? 

20050914, 01:26  #4 
Oct 2004
tropical Massachusetts
69_{10} 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 bogstandard written as a sextic in .... Last fiddled with by trilliwig on 20050914 at 01:29 
20050914, 14:55  #5  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}·937 Posts 
Quote:
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. 

20050915, 06:46  #6 
Oct 2004
tropical Massachusetts
3·23 Posts 
Hm, I can get close, but no cigar.
Code:
? Nfull=2^1378+1 ? L=2^6892^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^12eval(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 but it leaves a HUUGE constant coefficient , which is 186 digits, not much smaller than the SNFS difficulty at 191.5. 
20050916, 03:10  #7 
"William"
May 2003
New Haven
3·7·113 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^{689} + 2^{345} + 1 I understand that this is x^{13} + 2^{27}x^{6} + 1 where x=2^{53} 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^{12}+2ax^{11}+(4a+1)x^{10}+(3a+1)x^{9}+a*x^{8}+2ax^{7} +(4a+26843547)x^{6} +ax^{5}+2ax^{4}+(4a+1)x^{3}+(3a+1)x^{2}+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^{12}+2ax^{11}+4ax^{10}+8ax^{9}+16a*x^{8}+32ax^{7} +(64a+16642)x^{6} +abx^{5}+2abx^{4}+4abx^{3}+8abx^{2}+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. 
20050916, 11:24  #8 
May 2003
Warsaw
3·5 Posts 
Here are my calculations.
We can represent 2,1378M as y^{13}+xy^{6}+1, where y=2^{53} and x=2^{27}. 2,26L is yx+1. Now dividing y^{13}+xy^{6}+1 by yx+1 and taking advantage of an equality x^{2}=2y we get A(y)+xB(y), where A(y)=y^{12}+y^{11}y^{10}y^{9}+y^{8}+y^{7}y^{6}+y^{5}+y^{4}y^{3}y^{2}+y+1 B(y)=y^{11}y^{9}+y^{7}+y^{4}y^{2}+1 A(y) and B(y) are symmetrical so we reduce the coeffs by representing poly with root z=2^{27}+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 
20050916, 12:28  #9  
"Bob Silverman"
Nov 2003
North of Boston
2^{3}·937 Posts 
Quote:
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? 

20050916, 12:43  #10  
"Bob Silverman"
Nov 2003
North of Boston
16510_{8} Posts 
Quote:
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]) 

20050916, 13:24  #11  
May 2003
Warsaw
3·5 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Polynomial Discriminant is n^k for an n1 degree polynomial  carpetpool  Miscellaneous Math  14  20170218 19:46 
How to use my own polynomial with Msieve  jordis  Msieve  22  20090417 10:54 
5^4211 polynomial search  fivemack  Factoring  61  20080721 11:16 
Guess the Polynomial  Kevin  Puzzles  15  20070925 17:22 
[Need help] about Matrix Polynomial  buan  Homework Help  3  20070717 15:07 