Let's say one has an isogeny $\alpha:E_1\to E_2$ between two elliptic curves, and that $\ker\alpha$ is known. If there is a point $S_2\in E_2$, is there an efficient way to find its preimage $S_1\in E_1$ (where $\alpha(S_1)=S_2$) or any multiple of the preimage, on $E_1$?

I know that one possibility would be to compute the map of $S_2$ using the dual isogeny, i.e. that $\hat\alpha(S_2)=[\deg\alpha]S_1$, but then one would first need to generate and compute the dual isogeny $\hat\alpha$. I was wondering if there is a faster way, e.g. by analysing the action of $\alpha$ on different points or something I haven't thought of yet?

Thank you for your help!


Finding the preimage of an arbitrary point is equivalent to evaluating the dual isogeny on the point. Your question shows that if you can compute dual isogenies then you can compute preimages. Conversely, if you can evaluate preimages, then you can multiply by the degree of the isogeny to evaluate the dual isogeny. Therefore one should not expect to be able to evaluate preimages any faster than one can evaluate the dual isogeny.

  • $\begingroup$ That's what I feared. Thank you for your answer! $\endgroup$ – Gemeis Jul 16 at 7:41

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.