# How to find kernel of isogeny from the dual isogeny

Let $$E$$ be a supersingular elliptic curve over $$\mathbb{F}_{p^2}$$, where $$p = \ell_A^{e_A} \ell_B^{e_B} f \pm 1$$ for some primes $$\ell_A, \ell_B$$. Let $$R \in E[\ell_A^{e_A}]$$ be a point of order $$\ell_A^{e_A}$$ and suppose $$\phi:E \to E' = E/\langle R \rangle$$ is an isogeny with kernel $$\langle R \rangle$$. Let $$\widehat{\phi}:E' \to E$$ be the dual isogeny.

My question is: suppose we know the kernel of $$\widehat{\phi}$$, say $$\langle S \rangle$$. How can we recover $$\langle R \rangle$$?

• It looks similar to some kind of homework, can you provide some a bit of background on where you encounter this problem? Also, can you explain why you feel this is more cryptography than purely mathematics? Oct 30, 2019 at 8:10
• @DannyNiu This kind of questions shows up in isogeny-based cryptography, specifically SIDH/SIKE. Oct 30, 2019 at 9:05
• Hint: Consider another point $Q\in E'$ such that $\{S,Q\}$ is a basis of the $\ell_A^{e_A}$-torsion of $E'$ and look how $\phi\circ\widehat\phi$ acts on these points. Oct 30, 2019 at 9:11
• my guess (cmiiw) is that $\ker(\phi) = \langle \widehat{\phi}(Q) \rangle$ because $\phi(\widehat{\phi}(Q)) = [\ell_A^{e_A}]Q =$ identity. However, it is still unclear to me why should $\langle \widehat{\phi}(Q) \rangle = \langle R \rangle$.
– tfp
Oct 30, 2019 at 9:24
• @tfp You are right that $\ker(\phi)=\langle\widehat\phi(Q)\rangle$, but your argument only shows the $\supseteq$ inclusion. Re: "why should $\langle\widehat\phi(Q)\rangle=\langle R\rangle$", note that you've assumed $\ker(\phi)=\langle R\rangle$. Oct 31, 2019 at 12:29

We have that $$R \in E$$ is a point of order $$\ell_A^{e_A}$$, generating the kernel of $$\phi$$. Because $$\ell_A^{e_A}$$ is coprime to $$p$$, the $$\ell_A^{e_A}$$-torsion subgroup of $$E$$ has the following structure:

$$E[\ell_A^{e_A}] \cong \frac{\mathbb{Z}}{\ell_A^{e_A}\mathbb{Z}} \times \frac{\mathbb{Z}}{\ell_A^{e_A}\mathbb{Z}}.$$

Thus, as we know, two independent points of order $$\ell_A^{e_A}$$ generate $$E[\ell_A^{e_A}]$$. So there are points of order $$\ell_A^{e_A}$$ in $$E[\ell_A^{e_A}]$$ which are independent of $$R$$ - call one of them $$Q$$. That is, the kernels generated by $$R$$ and $$Q$$ only intersect trivially.

Now consider what happens when $$Q$$ is mapped via $$\phi$$, giving $$\phi(Q) \in E'$$. Because the subgroup $$\langle Q \rangle$$ only intersects trivially with $$\langle R \rangle = \ker \phi$$, and because isogenies are group homomorphisms, $$\phi(Q)$$ must have order $$\ell_A^{e_A}$$ on $$E'$$.

We also have that $$\widehat{\phi} \circ \phi = [\ell_A^{e_A}],$$ which is the multiplication-by-$$\ell_A^{e_A}$$ endomorphism on $$E$$. See, for example, Silverman's "The Arithmetic of Elliptic Curves" Section III.6 for proof of this fact and other facts about the dual isogeny. By definition, the kernel of the above endomorphism $$[\ell_A^{e_A}]$$ must be $$E[\ell_A^{e_A}]$$ - all the points which when multiplied by $$\ell_A^{e_A}$$ give the identity $$\mathcal{O}_E$$. This includes $$Q$$. So $$\phi(Q)$$ must be in the kernel of $$\widehat{\phi}$$.

So, because $$Q$$ is a point of order $$\ell_A^{e_A}$$ in the kernel of $$\widehat{\phi}$$ (an isogeny of degree $$\ell_A^{e_A}$$), it must generate said kernel. This gives us exactly what you wanted: a generator of the kernel of the dual isogeny. Simply map an independent point of the correct order through $$\phi$$ to get a generator of $$\ker \widehat{\phi}$$.

The same applies in the other direction: Given $$S$$ generating the kernel of $$\widehat{\phi}$$, we can pick a point of order $$\ell_A^{e_A}$$ independent of $$S$$ on $$E'$$ and map it through $$\widehat{\phi}$$ to get a point of order $$\ell_A^{e_A}$$ on $$E$$, in the kernel of $$\phi$$. This point must generate the kernel (it won't necessarily be equal to $$R$$, but it will be in the subgroup generated by $$R$$).