Timeline for Algorithms for finding rational points on an elliptic curve?
Current License: CC BY-SA 2.5
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 21, 2010 at 8:49 | comment | added | Charles Matthews | It was something Manin included in an old paper in Russian Mathematical Surveys. Attributed to Shafarevich, if I recall correctly. Manin said "if this is a joke, it is a gloomy one", or suchlike. | |
| Nov 20, 2010 at 21:33 | comment | added | William Stein | "You haven't heard the one about showing Birch-Swinnerton-Dyer unprovable by showing the rank is not computable?" Huh???! What the heck are you talking about? Assuming rank(E)<=1 or Sha(E)[p^oo] finite for one p, or BSD rank is true, then there is a deterministic algorithm to compute E(Q). Without making one of those assumptions, we still don't know. | |
| Oct 13, 2010 at 15:52 | comment | added | Charles Matthews | You haven't heard the one about showing Birch-Swinnerton-Dyer unprovable by showing the rank is not computable? Of course it is misleading here to mix up different kinds of algorithms. Brute force search will find a rational point on a curve if it is exists (partial correctness). A correct algorithm is what people generally mean by something being "algorithmic". A good probabilistic algorithm is typically what is sought in computational number theory, and a good algorithm with correctness proof conditional on some known conjecture is of real interest. | |
| Oct 13, 2010 at 15:18 | comment | added | Alex B. | Charles, there are deterministic algorithms. They often rely on unproven conjectures, but they happen to work very well in practice. Also, probabilistic algorithms are referred to as "algorithms", just as deterministic ones, and I don't quite see what is misleading about this terminology. | |
| Oct 13, 2010 at 14:59 | history | answered | Charles Matthews | CC BY-SA 2.5 |