Let $q$ be a prime power and let $m$ be a positive integer coprime to $q$. Further, let $E_1(\mathbb F_q)$ and $E_2(\mathbb F_q)$ be two isogenous supersingular elliptic curves over a finite field $\mathbb F_q$ such that

$$E_i(\mathbb F_q)[m] \cong \mathbb Z/m\mathbb Z \times \mathbb Z/m\mathbb Z$$

for $i = 1, 2$. Suppose that an isogeny $\phi \colon E_1 \rightarrow E_2$ is separable and has degree coprime to $m$. So in particular $\phi$ is a one-to-one and onto map between $E_1[m]$ and $E_2[m]$.

Now suppose that you are given a pair of generators $P,Q$ of $E_1[m]$ and a pair of generators $R,S$ of $E_2[m]$. In this setting, I have three questions.

  1. For which matrices

$$ \left( \begin{matrix} a & b\\ c & d \end{matrix} \right) \in \operatorname{GL}_2(\mathbb Z) $$

does there exist an endomorphism $\sigma \colon E_1 \rightarrow E_1$ such that $\sigma(P) = aP+bQ$ and $\sigma(Q)=cP+dQ$?

  1. How hard is it to answer the following question: does there exist an isogeny $\phi \colon E_1 \rightarrow E_2$ such that $\phi(P)=R$ and $\phi(Q) = S$? Of course in general it is difficult to compute $\phi$, but perhaps answering this question of existence is easier?

  2. Given a matrix

$$ \left( \begin{matrix} a & b\\ c & d \end{matrix} \right) \in \operatorname{GL}_2(\mathbb Z) $$

and a fact that $\phi(P)=R$ and $\phi(Q)=S$ for some isogney $\phi$, does there exist an isogeny $\phi'$ such that $\phi'(P) = aR+bS$ and $\phi'(Q)=cR+dS$? For which matrices is this possible?


1 Answer 1


Any endomorphism of $E[m]$ (as an abelian group) can be obtained as the restriction of an endomorphism of $E$ (as an elliptic curve). This is proved in the proof of Theorem 42.1.9. of John Voight's upcoming book Quaternion algebras.

Let $O = \operatorname{End}_{\mathbb{F}_q} E$ be the ring of endomorphisms defined over $\mathbb{F}_q$. Suppose that $\operatorname{rk}_\mathbb{Z} O= 4$. (If $\operatorname{rk}_\mathbb{Z} O< 4$ you will need to enlarge the field so that $\operatorname{End}_{\mathbb{F}_q} E$ is the full endomorphism ring.) Then $E[m]$ is an $O / mO$-module and the structure map $$ O / mO \to \operatorname{End} E[m] $$ is an isomorphism, where $\operatorname{End} E[m] \cong \operatorname{M}_2(\mathbb{Z} / m \mathbb{Z})$ is the endomorphism ring of $E[m]$ as an abelian group.

The structure map is injective since if $\phi \in O$ annihilates $E[m]$ then it must factor through $[m]$ and it is surjective since $\# O / mO = m^4 = \# \operatorname{M}_2(\mathbb{Z} / m \mathbb{Z}) = \# \operatorname{End} E[m]$.

This means the answer to the first question is yes, for any matrix there is a corresponding isogeny which acts on $E_1[m]$ the same way the matrix does.

For the second question, there always exists an isogeny $\psi : E_1 \to E_2$ such that $\deg \psi$ is coprime to $m$, hence the restriction of $\psi$ to $E_1[m]$ gives an isomorphism $E_1[m] \to E_2[m]$. So $\psi(P)$ and $\psi(Q)$ form a basis for $E_2[m]$ and, from the argument above, there exists some endomorphism $\alpha : E_2 \to E_2$ that maps $\psi(P)$ to $R$ and $\psi(Q)$ to $S$. Then the isogeny $\alpha \circ \psi : E_1 \to E_2$ is the desired isogeny, i.e. $\alpha \circ \psi(P) = R$ and $\alpha \circ \psi(Q) = S$. Finding $\psi$ is definitely difficult in general and finding $\alpha$ shoud also be difficult since computing the endomorphism ring of $E_2$ is believed to be difficult.

For the third question the answer is yes because you can postcompose $\phi$ with an appropriate endomorphism.


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.