Find isogeny between two given points

Question

Let $P$ be a point on an elliptic curve $E$ and let $Q = \phi(P)$, where $\phi: E \to E'$ is an isogeny of degree $d$.

Given $E, E', P, Q$ and $d$, is it possible to find an isogeny $\phi': E \to E'$, not necessarily equal to $\phi$, such that $\phi'(P) = Q$?

If so, how? And what is the complexity of such an algorithm?

Follow up question: if it is possible, it is also possible for two pairs of points?

Are $E$ and $E'$ given as well? If not, in what sense can one be given (say) $P$ but not $E$? — djao, May 14 '19 at 13:05
@djao $E$ and $E'$ are also given, sorry for not mentioning it in the question. — Andrea, May 14 '19 at 16:50

score 1 · Accepted Answer · answered May 15 '19 at 02:42

1

Given $E$, $E'$, and $d$, to find any isogeny $\phi\colon E \to E'$ of degree $d$ in general takes $O(d)$ time (arXiv:cs/0609020) using the current fastest known approach. It seems unlikely to me that the "extra" information of $P$ and $Q$ would make any difference.

Note that the combination of domain, codomain, and isogeny degree forms a very powerful constraint on the isogeny. I'm not sure, but I think in most natural situations (those where $d$ is not abormally large) this information would uniquely specify the isogeny up to automorphism, so $(E, E', d)$ alone would narrow the isogeny down to a small finite list of possibilities (no more than six), even without knowing $P$ and $Q$.

answered May 15 '19 at 02:42

djao

1,119

Does this change if $E =E'$, i.e. $\phi$ is an endomorphism? – Andrea May 23 '19 at 17:33
$\deg$ is a positive definite quadratic form on $\operatorname{Hom}(E_1, E_2)$ (Silverman III.6.3), so there are finitely many isogenies for each $E,E',d$. It's analogous to asking for the number of ways to write a fixed positive integer as a sum of four squares. Taking $E=E'$ makes no difference. – djao May 24 '19 at 19:01

Find isogeny between two given points

1 Answers1

Linked