Existence of an isogeny which maps between specified torsion bases

Question

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

2. 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?

3. 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?

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.