20051117, 12:41  #1 
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^(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). *trivial* results? 
20051117, 15:00  #2 
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^(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) 
20051117, 17:03  #3  
"Bob Silverman"
Nov 2003
North of Boston
2·3^{3}·139 Posts 
Quote:
This looks interesting. I will get back to you. 

20051118, 10:28  #4  
Nov 2005
5 Posts 
Quote:
Exactly this elliptic curve seems bad luck: Code:
# sage code # sage: run i program n0=5 n=2**(2**n0)+1 ii=2**(2**(n01)) s1=2**(2**(n02)) 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**2y2**2x1,2*x2*y2y1) if (2*x2*y2y1 == 0 or x2*y22*y1): al=(x2+ii*y2)%n al2=(x2ii*y2)%n ra=int(sqrt(x1+y1*ii))%n ro2=(x2ra)/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) k*y^2=x^3+a*x^2+b*x+c may be of use. 

20051118, 15:45  #5  
Nov 2005
5_{10} Posts 
Quote:
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. 

20051120, 12:22  #6 
Nov 2005
5_{10} 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^2yy^2)/xx0%n zz=round(n/4)+42 b2=(xx0^2zz^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^2yy^2)/xx0%n zz=round(n/4)+42 b2=(xx0^2zz^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=cd^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*a2a3] ellisoncurve(e1,point1) \\ inverse to quartic \\u=(2*q*(x+c)d^2/(2*q))/y \\v= q+u*(u*xd)/(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*x1d)/(2*q) a*u1^4+b*u1^3+c*u1^2+d*u1+q^2v1^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. 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Testing Mersenne Primes with Elliptic Curves  a nicol  Math  3  20171115 20:23 
Elliptic curve arithmetic  burrobert  GMPECM  6  20121108 13:05 
Need help with elliptic curves...  WraithX  Math  12  20100929 09:34 
Elliptic Curve Arithmetic  Raman  Math  8  20090413 19:20 
New coordinate system for elliptic curves  wpolly  GMPECM  5  20070718 13:18 