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.

  • 1
    Since this amounts to finding integer points on elliptic curves, you might want to look at [this MO question](http://mathoverflow.net/questions/42016/algorithms-for-finding-rational-points-on-an-elliptic-curve).2012-08-11
  • 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
    You seem totally unaware of the thing here involved, since I am specifically asking of a well-optimized algorithm for finding the integral points on an elliptic curve - and this calls for some details, although I will try to look after implementations in the package you mentioned.2012-08-11
  • 3
    I don't think I am - perhaps you might consider making your questions a little more precise! I can see no reference to "well-optimized algorithm for finding the integral points on an elliptic curve" in your question!2012-08-11
  • 0
    Look, any 11-year-old can come with "the solutions are bounded, look for them", but this gives rise to no "algorithm". Any contribution is welcome, but I **am very precise since the title of this topic** asks explicitly for **implemented** algorithms.2012-08-11
  • 6
    @ChindeaFilip I would be grateful that Old John tried to help, rather than call him ignorant and make rude comments. He is after all, very experienced and he did make the effort to help. And such behavior will only deter other potential answerers, since no one likes to be shouted at-**especially for helping**.2012-08-11
  • 4
    @ChindeaFilip: pari/gp implements the functions you need. The scripts suggested allow to initialize the different parameters required for your particular search (sage uses pari too). A typical script looks like {e= ellinit([0,0,0,0,-432*7^2],1) v= listcreate(10^4);for(x=0,10^4,s=ellordinate(e,x);if(#s, listput(v, [x,s[1]]))); v }2012-08-11
  • 0
    btw my previous script returns some $(x,y)$ solutions of $y^2= x^3 - 432\cdot 7^2$...2012-08-11
  • 0
    @RaymondManzoni This makes everything clear. Still, I don't like this particular answer, which seems just to disparage from the start any specialized solution in favor of general-purpose software.2012-08-11
  • 2
    @ChindeaFilip: Gerry's answer is fine too! Pari/gp is a number theory package (not only...) made by Henry Cohen and others ([Cohen](http://en.wikipedia.org/wiki/Henri_Cohen_(number_theorist)) is the author of quite some books concerning 'Computational (algebraic) Number Theory' this includes elliptic curves of course). 'pari' may be used too as an external library. Of course other solutions exist,2012-08-11
  • 1
    @RaymondManzoni Then, I must admit my ignorance here (see...), since I didn't imagine that this "popular" library was authored by Cohen himself (about whose books I know very well). +1!2012-08-11
  • 2
    @ChindeaFilip I guess *someone* deserves an apology, then.2012-08-17
  • 0
    @RaymondManzoni But this routine can be rather slow, for example if the smallest solution has $9$ digits. Does PARI/GP allow any acceleration ?2017-03-06
  • 0
    @Peter: the pari/gp script I provided requires indeed an execution time proportional to the number of $x$ terms tested (ellordinate taking nearly a constant time). A better general method may exist (possibly in Smart's book "The Algorithmic Resolution of Diophantine Equations" but I don't know it yet so...). Concerning pari's ellordinate function you may obtain a speedup of a factor $2.3$ by using the gp2c compiler, executing "gp2c-run -g gp2c.gp" with the gp2c.gp file containing the function $$-$$dEll(v,e,ma:small)=local(x:small);for(x=0,ma,s=ellordinate(e,x);if(#s, listput(v, [x,s[1]]))); v2017-03-06
  • 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