Timeline for Find special elliptic curves from j-invariant
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 23, 2016 at 17:26 | vote | accept | Meysam Ghahramani | ||
| Feb 23, 2016 at 0:07 | comment | added | Noam D. Elkies | Probably practical but not easy . . . e.g. find equations for $X_0(\ell)$ and the auxiliary information to find the isogenies it parametrizes, then try lots of rational points until eventually (in $O(\ell)$ tries) one of them yields an isogeny whose kernel consists of rational points. | |
| Feb 22, 2016 at 19:14 | comment | added | Joe Silverman | @NoamD.Elkies I know the OP asked for "deterministic", but I assumed that he/she wanted "practical deterministic". If one doesn't specify $j$, is there a practical way to find an $\mathbb F_p$ point on $X_1(\ell)$ if, say, $\ell$ is in the $10^3$ to $10^4$ range? | |
| Feb 22, 2016 at 19:11 | comment | added | Joe Silverman | @DavidLampert Good point, I did know that, but it slipped my mind. Of course, the main point is that the likely answer is that there are no such curves. | |
| Feb 22, 2016 at 15:52 | comment | added | David Lampert | I think $N(E',p) = 2(p+1)-N(E,p) (p \not= 2)$ is simpler. | |
| Feb 22, 2016 at 15:45 | comment | added | Noam D. Elkies | Note, though, that "find a non-square in GF(p)" is a notorious example of a problem that's very easily in RP but not known to be in P. (The OP didn't actually specify polynomial time, but if any deterministic algorithm is acceptable then one could even try all elliptic curves mod p . . .) | |
| Feb 22, 2016 at 15:36 | history | answered | Joe Silverman | CC BY-SA 3.0 |