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

[John Cremona <john.cremona@gmail.com>]

As Karim said, the Magma and Sage solutions are much more
sophisticated since they use a lot of elliptic curve theory to give a
complete set of solutions.

One very quick way of searching for solutions is to use Michael
Stoll's stand-alone C program "ratpoints" which is a very fast
quadratic sieve implementation which can search for rational solutions
to y^2=f(x) where f is an integer polynomial (of any degree).

For example:

john@ubuntu%time ./ratpoints  '-431 0 0 1' 1000000 -du 1 -q
(1 : 0 : 0)
(8 : 9 : 1)
(8 : -9 : 1)
(11 : 30 : 1)
(11 : -30 : 1)
(20 : 87 : 1)
(20 : -87 : 1)
(30 : 163 : 1)
(30 : -163 : 1)
(36 : 215 : 1)
(36 : -215 : 1)
(138 : 1621 : 1)
(138 : -1621 : 1)
(150 : 1837 : 1)
(150 : -1837 : 1)
(575 : 13788 : 1)
(575 : -13788 : 1)
(3903 : 243836 : 1)
(3903 : -243836 : 1)

real	0m0.005s
user	0m0.000s
sys	0m0.004s

Note that this takes a very short time indeed, and finds all solutions
with |x|<10^6.  (The command line parameters are: the coefficients of
f, the height bound, the denominator bound (=1 for integral points
only) and -q for non-verbose output.

The program can be obtained from
http://www.mathe2.uni-bayreuth.de/stoll/programs/index.html, is free
(GPL) and only requires gmp.

John Cremona

2009/6/18 cino hilliard <hillcino368@hotmail.com>:
> Hi Karim,
>
>> From: Karim.Belabas@math.u-bordeaux1.fr
>> Date: Thu, 18 Jun 2009 14:12:36 +0200
>> To: pari-users@list.cr.yp.to
>> Subject: Re: Elliptic curve x^3 - y^2 = p
>>
>> * cino hilliard [2009-06-18 12:35]:
>> > (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
>>
>> OK, that's for 2.4.3 only then :-(.
>>
>> (14:10) gp > ??setintersect
>> setintersect(x,y):
>>
>> intersection of the two sets x and y (see setisset). The function also
>> works
>> if both x and y are vectors of stricly increasing entries ( according to <
>> );
>> in that case we return a vector of strictly increasing entries, not a set.
>> Otherwise, the result is undefined.
> Oh boy.
> I always get
>
> Could not find translation file, docdir='C:/Program Files/PARI' at
> C:/Program
> Files/PARI/gphelp line 152.
>
> with  super help ??
>
>
>> For "older" versions than that, use
>>
>> setintersect(Set(vector(n,x,x^3-p)), Set(vector(n,y,y^2)))
>>
>> ( slower but not *much* slower... )
>
> Bravo!
> This does what I want.
>
>  diffcubes(n,p) =
>                          {
>                         local(j,x,y,c);
>                         a=eval(setintersect(Set(vector(n,x,x^3-p)),
> Set(vector(n,y,y^2))));
>                         c=length(a);
>                         a=vecsort(a);
>                         for(j=1,c,
>                         y=round(sqrt(a[j]));
>                         x=round((a[j]+p)^(1/3));
>                         print(j": "x"^3 - "y"^2 = "p); \\ Too fancy? Change
> it.
>                         );
>                         c;
>                         }
>
>
> (14:51:50) gp > diffcubes(300000,431)
> 1: 8^3 - 9^2 = 431
> 2: 11^3 - 30^2 = 431
> 3: 20^3 - 87^2 = 431
> 4: 30^3 - 163^2 = 431
> 5: 36^3 - 215^2 = 431
> 6: 138^3 - 1621^2 = 431
> 7: 150^3 - 1837^2 = 431
> 8: 575^3 - 13788^2 = 431
> 9: 3903^3 - 243836^2 = 431
> (15:02:35) gp > ##
>   ***   last result computed in 2,250 ms.
> (15:02:39) gp >
>
> This finds all instances because I new a prori 243836 was the big kahuna.
> I guess it will still be trial and error?
>
> Oh well, we are at least 2 quanta over what I had.
>
>  Thank you  >>>
> Cino
>
>