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

["Karim Belabas" <Karim.Belabas@math.u-bordeaux1.fr>]

* 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]
`