cino hilliard on Thu, 18 Jun 2009 12:53:29 +0200

 FW: Elliptic curve x^3 - y^2 = p A12-140

 Re-send  From: hillcino368@hotmail.comTo: pari-users@list.cr.yp.toSubject: RE: Elliptic curve x^3 - y^2 = pDate: Thu, 18 Jun 2009 05:28:53 -0500 Thanks for the help.  dell pentium 2.53 ghz windows xp pro                  GP/PARI CALCULATOR Version 2.3.4 (released)          i686 running cygwin (ix86/GMP-4.2.1 kernel) 32-bit versioncompiled: Jul 12 2008, gcc-3.4.4 (cygming special, gdc 0.12, using dmd 0.125)               (readline v5.2 enabled, extended help available)                    Copyright (C) 2000-2006 The PARI Group Karim, (05:26:04) gp > ?diffcubesdiffcubes(n,p)=local(x,y);setintersect(vector(n,x,x^3-p),vector(n,y,y^2)) getting this(05:20:04) gp > diffcubes(10000,431)  *** setintersect: not a set in setintersect. also for ver 2.4.2   > From: Karim.Belabas@math.u-bordeaux1.fr> Date: Thu, 18 Jun 2009 11:27:12 +0200> To: pari-users@list.cr.yp.to> Subject: 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]> `