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?

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

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$.

  • $\begingroup$ Does this change if $E =E'$, i.e. $\phi$ is an endomorphism? $\endgroup$ – Andrea May 23 '19 at 17:33
  • $\begingroup$ $\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. $\endgroup$ – djao May 24 '19 at 19:01

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.