# Find isogeny between two given points

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

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