cino hilliard on Thu, 18 Jun 2009 12:35:36 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

RE: Elliptic curve x^3 - y^2 = p


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 version
compiled: 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 > ?diffcubes
diffcubes(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]
> `