Thread: Polynomial
View Single Post
Old 2005-09-14, 14:55   #5
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22×5×373 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