mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2005-11-17, 12:41   #1
otkachalka
 
Nov 2005

1012 Posts
Default Elliptic curves in NFS

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):
Code:
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 is offline   Reply With Quote
Old 2005-11-17, 15:00   #2
otkachalka
 
Nov 2005

5 Posts
Default

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:

Code:
\\ 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)
otkachalka is offline   Reply With Quote
Old 2005-11-17, 17:03   #3
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

1C4016 Posts
Default

Quote:
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):
Code:
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.
R.D. Silverman is offline   Reply With Quote
Old 2005-11-18, 10:28   #4
otkachalka
 
Nov 2005

1012 Posts
Default

Quote:
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:

Code:
# 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 is offline   Reply With Quote
Old 2005-11-18, 15:45   #5
otkachalka
 
Nov 2005

5 Posts
Default

Quote:
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 is offline   Reply With Quote
Old 2005-11-20, 12:22   #6
otkachalka
 
Nov 2005

5 Posts
Default

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.

Code:
\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\
\\ 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.
otkachalka is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Testing Mersenne Primes with Elliptic Curves a nicol Math 3 2017-11-15 20:23
Elliptic curve arithmetic burrobert GMP-ECM 6 2012-11-08 13:05
Need help with elliptic curves... WraithX Math 12 2010-09-29 09:34
Elliptic Curve Arithmetic Raman Math 8 2009-04-13 19:20
New coordinate system for elliptic curves wpolly GMP-ECM 5 2007-07-18 13:18

All times are UTC. The time now is 01:55.

Mon Oct 26 01:55:40 UTC 2020 up 45 days, 23:06, 0 users, load averages: 1.81, 1.77, 1.68

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.