# Polynomial time algorithms for rank 1 elliptic curves over Q

As an outsider, it sounds like a lot of progress has been made on understanding rank 1 elliptic curves. Much of the BSD conjecture is known for rank 1, and Heegner points provide a way to calculate a rational point of infinite order on the curve.

However, as an outsider, it is hard to understand what properties are feasible to obtain computationally.

So I would like to know, given an elliptic curve in minimal Weierstrass form, and assuming the factors of the discriminant are known (so that we don't need to get into complexity of factoring), what properties can be efficiently calculated about the curve? (let efficient = calculating in a time polynomial of the data size of values specifying the minimal model of the curve.)

• Discriminant - yes, obviously
• Conductor - it sounds like yes, if you know the factors of the discriminant? (I don't fully understand this concept yet, so may be misunderstanding some details (especially regarding the different notations that include a 16 or not in the discriminant). But it sounds like Tate's algorithm is sufficient to obtain the conductor if we have the factors of the discriminant.)
• Torsion points - it sounds like yes, if you know the factors of the discriminant, via Nagell-Lutz theorem
• Determine if curve is at least rank 1 - Sounds like yes, via computing the sign of the functional equation related to the L function (called the "global root number"? Not sure how computing this works, but sounds like info from Tate's algorithm is enough? see this Determining elliptic curve analytic rank even/odd )
• Determine if curve is rank 1 - For rank 1 it is known this can be checked from analytic rank, but I don't know time complexity of calculating this.
• Calculate a rational point of infinite order - Heegner points work for rank 1, but I don't know if there are more efficient ways, or what is the computational complexity of calculating Heegner points.
• Calculating a basis point modulo torsion - ?? At least as hard as the above.
• Calculating a basis point modulo torsion, given a rational point of infinite order - ?? Possibly simpler than above. Again, unsure what the best algorithms are.
• Details of Tate–Shafarevich group - Unfortunately, I don't even know what this is, or is used for. But it is commonly referred to in some computational packages. It is referred to in BSD conjecture, so may be resolved for rank 1 now? Although, I'm unsure complexity of calculating the necessary derivative of the L function.
• Details of Selmer group - Commonly referred to in some computational packages.
• Other useful properties ...

It is likely there is an amazing intro in some review paper that I haven't found yet, which covers all of this. That would be perfect.

Of most interest to me are the computations of the rank and finding a point of infinite order. For point finding I've tried looking into the internals of some libraries, but it looks like a lot of them do something to limit a search range and then do a lot of searching (its very possible I am mistaken here). This quickly becomes daunting for larger values, and am unsure if nothing better is known, or if algorithms that scale well just run way too slow for the small values so are not useful for most calculations.

In short, it would be nice to have a quick run down of what currently is and is not computationally efficient for basic properties of rank 1 elliptic curves over Q.

• Perhaps Theoretical Computer Science is more appropriate for this question. – Yuval Filmus Jan 26 '19 at 6:36
• – orlp Jan 26 '19 at 13:26
• @orlp Elliptic curves for crypto are over a finite field, and finding a point there is not an issue. Over Q it can be difficult to even find a point (and with rank=0, there may be no points to find). – PluckyBird Jan 28 '19 at 18:55
• @YuvalFilmus I do not understand the difference between the sites. I still learning the terminology even, and am definitely not at the gradschool or researcher level. I wish the distinction was made clearer for new comers. Anyway, could you migrate the question? Or should I just repost? – PluckyBird Jan 28 '19 at 18:57
• You can flag it for migration. – Yuval Filmus Jan 29 '19 at 2:33