Karim Belabas on Thu, 18 Jun 2009 11:28:59 +0200 |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Elliptic curve x^3 - y^2 = p |
* cino hilliard [2009-06-18 10:59]: > I want to find the number of solutions of the elliptic curve, x^3 - y^2 = p > > for various p = 7, 431, 503, etc > > > > I have been using brute force in a Pari script below testing for solutions. > > diffcubesq2(n,p) = > { > local(a,c=0,c2=0,j,k,y); > for(j=1,n, > for(k=1,n, > y=j^3-k^2; > if(y==p, > c++; > print(j","k","y); > ); > ); > ); > c; > > } > > > diffcubesq2(10000,431) outputs > > 8,9,431 > 11,30,431 > 20,87,431 > 30,163,431 > 36,215,431 > 138,1621,431 > 150,1837,431 > > (03:14:10) gp > ## > *** last result computed in 6mn, 57,969 ms. Here's a "simpler" and better approach (still naive) for your problem: diffcubes(n, p)= setintersect(vector(n, x, x^3 - p), vector(n, y, y^2)); (11:15) gp > diffcubes(10000,431) time = 10 ms. %2 = [81, 900, 7569, 26569, 46225, 2627641, 3374569] I trust you can work out the individual solutions (x,y) from the above data :-) For each given p, you can certainly work out necessary congruence conditions and restrict to arithmetic progressions for linear speedups. > My Pari code misses the last two solutions. It would have > > taken way too much time to get to y = 243836 anyway. (11:19) gp > diffcubes(243836, 431) time = 130 ms. %3 = [81, 900, 7569, 26569, 46225, 2627641, 3374569, 190108944, 59455994896] > I tried using the Magma applet to compute the elliptic curve. > This gets all solutions in a fraction of the time. [...] > E := EllipticCurve([0, -7]); > Q, reps := IntegralPoints(E); This is a much more sophisticated algorithm, involving computing the full Mordell-Weil group, then transcendence methods (linear forms in elliptic logarithms + de Weger's reduction). Cheers, K.B. -- Karim Belabas, IMB (UMR 5251) Tel: (+33) (0)5 40 00 26 17 Universite Bordeaux 1 Fax: (+33) (0)5 40 00 69 50 351, cours de la Liberation http://www.math.u-bordeaux1.fr/~belabas/ F-33405 Talence (France) http://pari.math.u-bordeaux1.fr/ [PARI/GP] `