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.

$\endgroup$
  • 1
    $\begingroup$ Since this amounts to finding integer points on elliptic curves, you might want to look at this MO question. $\endgroup$ – Zhen Lin Aug 11 '12 at 8:46
  • 5
    $\begingroup$ I down-voted for rudeness. $\endgroup$ – Fred Kline Aug 11 '12 at 10:42
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Chindea Filip Aug 11 '12 at 11:42
6
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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! $\endgroup$ – Old John Aug 11 '12 at 8:27
  • 6
    $\begingroup$ @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. $\endgroup$ – Ravi Aug 11 '12 at 8:43
  • 4
    $\begingroup$ @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 } $\endgroup$ – Raymond Manzoni Aug 11 '12 at 8:56
  • 2
    $\begingroup$ @ChindeaFilip: Gerry's answer is fine too! Pari/gp is a number theory package (not only...) made by Henry Cohen and others (Cohen 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, $\endgroup$ – Raymond Manzoni Aug 11 '12 at 12:02
  • 2
    $\begingroup$ @ChindeaFilip I guess someone deserves an apology, then. $\endgroup$ – Pedro Tamaroff Aug 17 '12 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.