Thread: What's next? View Single Post
2005-05-12, 19:30   #14
dleclair

Mar 2003

10011012 Posts

Hi Bob,

Quote:
 Actually, the *really* interesting question is whether the number would be faster with SNFS or GNFS. SNFS lets us take advantage of the algebraic factor 2^152+1, but requires a quartic, which is sub-optimal for numbers this size.
Using the (only) trick I know I get a quadratic and a linear:

f(x) = x^2 - x - 1
g(x) = 2^152*x-2^304-1
x=(2^152+1/2^152)

Clever selection of polynomials is certainly not my forte and I've probably missed something.

Any tips?

Here is PARI code to show the process I used to reach the quadratic and linear:

Code:
x^608 - x^456 + x^304 - x^152 + 1

y=x^152

y^4 - y^3 + y^2 - y + 1

(y^4 + y^2) - (y^3 + y) + 1

(y^4 + y^2) - (y^3 + y) + 1

( (y^4 + y^2) - (y^3 + y) + 1 ) / y^2

( (y^2 + 1) - (y^1 + y^-1) + y^-2 )

y^2 + 1 - y^1 - y^-1 + y^-2

y^2 + y^-2 - (y^1 + y^-1) + 1

z=y+y^-1

y^2 + y^-2 - z + 1

z^2= (y^2 + y^-2 + 2)

z^2 - 2 - z + 1

z^2 - z - 1

n=(2^760+1)/(2^152+1)

f(x) = x^2 - x - 1
g(x) = 2^152*x-2^304-1

m=(2^152+1/2^152)

f(m)%n
g(m)%n
-Don