2005-09-14, 14:55   #5
R.D. Silverman

Nov 2003

22×5×373 Posts

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.