mersenneforum.org Elliptic curves in NFS
 Register FAQ Search Today's Posts Mark Forums Read

 2005-11-17, 12:41 #1 otkachalka   Nov 2005 5 Posts 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?
 2005-11-17, 15:00 #2 otkachalka   Nov 2005 5 Posts 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)
2005-11-17, 17:03   #3
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

2·33·139 Posts

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.

2005-11-18, 10:28   #4
otkachalka

Nov 2005

5 Posts

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.

2005-11-18, 15:45   #5
otkachalka

Nov 2005

510 Posts

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.

 2005-11-20, 12:22 #6 otkachalka   Nov 2005 510 Posts 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post a nicol Math 3 2017-11-15 20:23 burrobert GMP-ECM 6 2012-11-08 13:05 WraithX Math 12 2010-09-29 09:34 Raman Math 8 2009-04-13 19:20 wpolly GMP-ECM 5 2007-07-18 13:18

All times are UTC. The time now is 02:39.

Sat Jan 28 02:39:31 UTC 2023 up 163 days, 8 mins, 0 users, load averages: 0.74, 0.84, 0.96