# Computing explicit isogenies between elliptic curves over different kinds of fields

I have some questions about isogenies of elliptic curves in two settings:

1. Elliptic curves defined over the rationals.

1.1. Given two elliptic curves $$E/\mathbb{Q}$$ and $$E'/\mathbb{Q}$$ we can decide if they are $$\mathbb{Q}$$-isogenous. One way to do it is to use Mazur's theorem to bound the degree of possible isogenies for $$E$$. Then we can construct all isogenies up to that degree (can this be done by Velu's formulæ?) and the corresponding isogenous curves (up to isomorphism). Finally, we can check if $$E'$$ is isomorphic to one of these (finitely many) curves. I believe Magma can do this.

1.2. It seems to me that the above procedure outputs the isogeny between $$E/\mathbb{Q}$$ and $$E'/\mathbb{Q}$$ if they are isogenous.

2. Elliptic Curves over a finite field $$k$$

2.1. Deciding if two elliptic curves are isogenous is easy due to Tate's isogeny theorem which says that elliptic curves over finite fields are isogenous iff the order of their set of $$k$$-points is the same.

2.2. Is there any way to tell the degree of this isogeny? Is there any way to list all of the isogenies of an elliptic curve over a finite field? I know that computing the isogeny itself is very difficult as many cryptosystems depend precisely on the hardness of this problem. However, I would be interested in what is the best that we can do, what are the techniques and what are the difficulties (in comparison to the rational case).

• Over $\mathbb{Q}$ you should start by comparing the conductor of the two curves by Tate's algorithm, then comparing $a_p$ for primes $p$ of good reduction. That will already prove if $E$ and $E'$ are isogenous over $\mathbb{Q}$. Looking at the image of the Galois representation on $T_pE$ using the $a_p$ again, you can detect all isogenies leaving $E$ and so it is easy to find the isogeny. This all generalises to number fields and it is implemented in Sage. Commented May 19, 2023 at 8:23

For 1.1 and 1.2: Vélu's formulae require the kernel of the isogeny, or the polynomial whose roots are the $$x$$-coordinates of the nontrivial kernel points. If you don't know the isogeny in advance, but you have a list of candidate degrees, then you would probably do better to check for the existence of isogenies $$E \to E'$$ of each degree using modular polynomials first. You could then apply Elkies' algorithm to reconstruct the isogeny, which covers 1.2 as well. There is an accessible introduction to this in Section 7 of Schoof's Counting points on elliptic curves over finite fields.
For 2.2: the degree is not unique. Currently we have no efficient way of identifying the set of degrees, or the minimal degree, for general $$(E,E')$$.