0
$\begingroup$

I admit I have no idea how to tag this post, but I'm looking for a CAS/number theory software package that would implement a decent algorithm for computing the integral solutions to

$x^2 = y^3 - k$,

$k \in \mathbb{Z}_+$ a parameter taking values up to order of $10^5-10^6$, say? Since these are so frequent in "math contests", it would be a help for people working with such things, not to say that it's also of interest in itself.

This came to my mind some time ago and it'll be nice to see it implemented somewhere, since I couldn't find anything of the kind. Maybe I should try in a cryptography-related area, but where to start?

You can close this if software recommendations are contrary to the site rules. If this is "too localized" and trivial, at least I'd like to know if it stays within the confines of classical elliptic curves theory and algorithms.

  • 5
    I down-voted for rudeness.2012-08-11

2 Answers 2

4

Maple has a package called ellpack for handling elliptic curves. Also if you type $\rm Cremona\quad elliptic$ into the web, many useful links will appear.

I also recommend the paper, Gebel, Petho and Zimmer, On Mordell's equation. According to the summary, they solve Mordell for all $k$ up to 10,000, so you may be asking for a bit much if you want to go up to 1,000,000.

  • 0
    Thank you very much! +1, I had no idea how to search for those packages. Incidentally, I also have one older paper by Gebel, Petho and Zimmer (1997), on the very same subject - this makes me wonder why this is so "obscure" while it should not be.2012-08-11
6

For numbers of the size you mention, and that are likely to appear in problems in contests, you will be able to find all the solutions you need, with just a tiny bit of programming using the package Pari/GP which is freely available and runs under various different operating systems. It can be downloaded from here.

I have found it to be a very fast and convenient package for many different types of number theory investigations (from elementary to pretty advanced), so it would probably be more useful than something which is designed to solve just the Mordell-type equations.

  • 0
    For $ma=10^9$ my old $2.3$GHz computer needed $15$ mn (I think that a factor $5$ could be gained with a modern Xeon at 4GHz). Concerning gp2c you may see this [tutorial](http://pari.math.u-bordeaux.fr/~bill/GP2C/node2.html). Better methods should exist...2017-03-06