Elliptic curves in NFS

otkachalka_at_hushmail.com
Date: 11/17/05


Date: 17 Nov 2005 06:02:30 -0800

Here is a probably useless relation between elliptic curves and NFS.
Consider a NFS with polynomial of degree 2.
The product of the rational and the algebraic sides is of the form:
x^3+a*x^2+b*x+c
Consider the elliptic curve

y^2=x^3+a*x^2+b*x+c
If one knows a rational point on this elliptic curve, by multiplying
the point
rational (x,y) may be generated.

The case for Fermat numbers seems interesting (PARI session):

For example F5:
n0=5
n=2^(2^n0)+1
ii=2^(2^(n0-1))
s1=2^(2^(n0-2))

po=(x^2+1)*(x+ii) == x^3 + 65536*x^2 + x + 65536
the point1=[0,s1] is on the curve.
3*point1 generates
[x1/y1,z1] ==
[9007199255265280/295147905144993087489,-1298074215313727680749415876788992/5070602400027473890500293951487]
factor(x1^2+y1^2)
%26 =
[12049 2]

[24495634930901489 2]

factor(x1+ii*y1)
%27 =
[2 16]

[13 2]

[463 2]

[2854273 2]

factor(y1)
%28 =
[3 2]

[43691 2]

[131071 2]

gcd(x1,y1)
%30 = 1

so both the norm and the rational side are squares and in addition y1
is square
(all in Z).

Is there an analytical explanation that these "squares" will lead to
*trivial* results - because the squares seem the final stage of NFS
with the
 sieving skipped in the case of Fermat numbers ?

\\ PARI code
n0=5
n=2^(2^n0)+1
ii=2^(2^(n0-1))
s1=2^(2^(n0-2))
mod(ii^2,n)
po=(x^2+1)*(x+ii)
e1=ellinit([0,ii,0,1,ii])
point1=[0,s1]
ellisoncurve(e1,point1)
po2=ellpow(e1,point1,3)
x1=numerator(po2[1])
y1=denominator(po2[1])
z1=po2[2]
al=(x1^2+y1^2)
ra=(x1+ii*y1)
\\factor(al)
\\factor(ra)
\\factor(y1)



Relevant Pages

  • Re: Simultaneous square trinoms
    ... Obviously Pumpster's solution trumps any laborious transforms ... and general fiddling about. ... I imagine Pumpster's elliptic curve is birationally equivalent ... appearing in the above sum of squares identity. ...
    (sci.math)
  • Re: Simultaneous square trinoms
    ... Does it exist a simple way choice of to build such squares, ... Well, assuming you want c and d coprime, this is equivalent ... which is birational to the Weierstrass form ... problem is treated for an elliptic curve in quartic form like this ...
    (sci.math)
  • Re: A concrete Elliptic Curve
    ... which are on the elliptic curve ... It should be noted that the left hand term is the formula for the sum ... of the first n squares: ...
    (sci.math.research)