Elliptic curves in NFS

[otkachalka]

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?

[otkachalka]

If I understand correctly, having:
x1^2+y1^2 = s1^2
x1+ii*y1 = s2^2
gcd(x1,y1)=1
all in Z in the above example is the final stage of NFS with the sieving skipped.

Obviously a problem is if all points generate the trivial roots.

Can someone please try to verify if several points generate only the trivial solution for Fermat numbers?
( "I" in C should be replaced with "-ii" )

code for generating points:

\\ PARI code
\\ may need default(realprecision,10000)
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)

[R.D. Silverman]

Originally Posted by otkachalka

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?

This looks interesting. I will get back to you.

[otkachalka]

Originally Posted by R.D. Silverman

This looks interesting. I will get back to you.

Due to lameness I am not sure I got the homomorphism right - in the original example to what is sent the imaginary unit to "-ii" or to "+ii" ?

Exactly this elliptic curve seems bad luck:

# sage code
# sage: run -i program

n0=5
n=2**(2**n0)+1
ii=2**(2**(n0-1))
s1=2**(2**(n0-2))
e1=EllipticCurve([0,ii,0,1,ii])
point1=e1([0,s1])
po2=point1
for i in range(2,20):
  po2=po2+point1
  po2a=po2[0]
  x1=po2a.numerator()
  y1=po2a.denominator()
  x1a=x1
  y1a=y1
  t=(x1a+int(sqrt(x1a*x1a+y1a*y1a)))/y1a
  y2=t.denominator()
  x2=t.numerator()
#  print(i,x1,y1,x2,y2,x2**2-y2**2-x1,2*x2*y2-y1)
  if (2*x2*y2-y1 == 0 or x2*y2-2*y1):
	  al=(x2+ii*y2)%n
	  al2=(x2-ii*y2)%n
	  ra=int(sqrt(x1+y1*ii))%n
	  ro2=(x2-ra)/y2%n
	  print(i,al,ra,ro2,ro2**2%n)


sage: run -i v42.sag
(2, 4294967296, 1L, 0, 0)
(3, 65537, 4294967041L, 2621409, 4132437378)
(4, 1, 4294967296L, 4294885377, 2415919103)
(5, 65537, 4294967041L, 3206716853, 3431388664)
(6, 4294967296, 4294967296L, 4294901761, 4294967296)
(7, 65537, 256L, 3274361120, 3350793844)
(8, 1, 1L, 4294901761, 4294967296)
(9, 65537, 256L, 1617870607, 3676840878)
(10, 4294967296, 1L, 2170399585, 2010460612)
(11, 65537, 4294967041L, 2983524356, 3277819888)
(12, 1, 4294967296L, 164720951, 3950982274)
(13, 65537, 4294967041L, 2862696733, 497087122)
(14, 4294967296, 4294967296L, 4294901761, 4294967296)

Eventually curves of the type:

k*y^2=x^3+a*x^2+b*x+c

may be of use.

[otkachalka]

Originally Posted by otkachalka

Eventually curves of the type:

k*y^2=x^3+a*x^2+b*x+c

may be of use.

In case point multiplication is defined on curves of the type:
k*y^2=x^3+a*x^2+b*x+c
seems like some initial sieving may give us a point on the curve and k that may be large.

[otkachalka]

Looks like suitable elliptic curve and a point on it may be found for general numbers.

According to
http://en.wikipedia.org/wiki/Number_field_sieve
"We choose two irreducible polynomials f(x) and g(x) with common root m mod n;"

xx0=2
yy=round(n/3)+42
b1=(-xx0^2-yy^2)/xx0%n
zz=round(n/4)+42
b2=(-xx0^2-zz^2)/xx0%n
f(x)=x^2+b1*x+yy^2
g(x)=x^2+b2*x+zz^2

the common root is xx0.
xx0,yy and zz may be chosen at random in Z

f(u)*g(u) is monic quartic:
v^2=a*u^4+b*u^3+c*u^2+d*u + q^2
[u,v] == [0,q] is on the curve where q=yy*zz

This can be reduced to weierstrass form birationally.
Multiplication may be done on the elliptic curve and then transferred to
the quartic.

\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
\\ Copyright (C) 2005 otkachalka
\\ Distributed under the terms of the GNU General Public License (GPL)
\\
\\ The full text of the GPL is available at:
\\ http://www.gnu.org/licenses/gpl.txt

\\ quartic to weierstrass [1 - Introduction to Elliptic curves]
\\ v^2=a*u^4+b*u^3+c*u^2+d*u + q^2
\\ [u,v] == [0,q] on the curve

\\ to
\\x=(2*q*(v+q)+d*u)/u^2
\\y=(4*q^2*(v+q)+2*q*(d*u+c*u^2)-d^2*u^2/(2*q))/u^3
default(realprecision,10042)
n=2^(2^5)+1
\\n=30000091000003
xx0=2 \\1
yy=round(n/3)+42
b1=(-xx0^2-yy^2)/xx0%n
zz=round(n/4)+42
b2=(-xx0^2-zz^2)/xx0%n
po1=xx1^2+b1*xx1*yy1+yy^2*yy1^2
po2=xx1^2+b2*xx1*yy1+zz^2*yy1^2
\\[xx0,1] common root mon n
\\xx0,yy,zz may be chosen at random

a=1
b=b1+b2
c=b1*b2 + yy^2 + zz^2
d=(b2*yy^2 + b1*zz^2)

q=yy*zz

a1=(d/q)
a2=c-d^2/(4*q^2)
a3=2*q*b
a4= -4*q^2*a
a6=a2*a4

e1=ellinit([a1,a2,a3,a4,a6])
point1=[-a2,a1*a2-a3]
ellisoncurve(e1,point1)
\\ inverse to quartic
\\u=(2*q*(x+c)-d^2/(2*q))/y
\\v= -q+u*(u*x-d)/(2*q)
po2=ellpow(e1,point1,3)
x1=po2[1]
y1=po2[2]

u1=(2*q*(x1+c)-d^2/(2*q))/y1
v1= -q+u1*(u1*x1-d)/(2*q)

a*u1^4+b*u1^3+c*u1^2+d*u1+q^2-v1^2
xx1=numerator(u1)
yy1=denominator(u1)

po1=xx1^2+b1*xx1*yy1+yy^2*yy1^2
po2=xx1^2+b2*xx1*yy1+zz^2*yy1^2
issquare(po1*po2)
issquare(po1)
issquare(po2)

\\ Justification of windows usage is a combination of Stockholm
\\ Syndrome and cognitive dissonance.