Elliptic curves in NFS
otkachalka_at_hushmail.com
Date: 11/17/05
 Next message: David A. Scott: "Re: Base Conversion and Cryptology"
 Previous message: Mike  EMAIL IGNORED: "modifying ISAAC, a pseudorandom number generator"
 Next in thread: otkachalka_at_hushmail.com: "Re: Elliptic curves in NFS"
 Reply: otkachalka_at_hushmail.com: "Re: Elliptic curves in NFS"
 Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
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^(n01))
s1=2^(2^(n02))
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^(n01))
s1=2^(2^(n02))
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)
 Next message: David A. Scott: "Re: Base Conversion and Cryptology"
 Previous message: Mike  EMAIL IGNORED: "modifying ISAAC, a pseudorandom number generator"
 Next in thread: otkachalka_at_hushmail.com: "Re: Elliptic curves in NFS"
 Reply: otkachalka_at_hushmail.com: "Re: Elliptic curves in NFS"
 Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
