Can I find an endomorphism of an elliptic curve with a specific kernel size?

Question

Say I want to find an endomorphism of an ordinary elliptic curve $E$ with kernel size of a prime $l$ that divides the cardinality of $E$. Is this possible in its endomorphism ring and what is the proof?

Answer 1

Let $E$ be an ordinary elliptic curve defined over a finite field $\mathbb{F}_q$. An endomorphism of degree $\ell$ is exactly an element of $\operatorname{End}(E)$ of norm $\ell$, so an endomorphism of degree $\ell$ exists if and only if there exists an element in $\operatorname{End}(E)$ of norm $\ell$. (EDIT #1: Your question was about kernels of size $\ell$, which is usually, but not always, equivalent to isogenies of degree $\ell$. The exception is if the isogeny is inseparable. So we assume that you are looking for separable endomorphisms.)

Of course, a necessary condition for the existence of an element of norm $\ell$ is the existence of a prime ideal of norm $\ell$. This part is easy: A prime ideal of norm $\ell$ exists in $\operatorname{End}(E)$ if and only if $\operatorname{disc}(\operatorname{End}(E))$ is zero or a quadratic residue mod $\ell$.

Unfortunately, the above necessary condition is not sufficient. For the rest of this answer I will assume that we are in the fairly common case where $\operatorname{End}(E) \cong \mathbb{Z}[\sqrt{-D}]$ and $D$ is not zero mod $\ell$. (If you want to understand the other cases, you had better understand this case first; it's easier.) From the definition of norm, we know that $\ell$ is the norm of an element in $\operatorname{End}(E)$ if and only if $\ell$ is a prime of the form $x^2 + Dy^2$. An entire graduate textbook has literally been written on this exact topic (Primes of the form $x^2+ny^2$, by David Cox), so one should not expect any easy answers here. The eventual classification theorem proved in that book (Theorem 9.2) states that $\ell$ is of the form $x^2+Dy^2$ if and only if the following two things both hold:

1. $-D$ is a quadratic residue modulo $\ell$, and
2. The Hilbert class polynomial $H_{-4D}(X)$ of $\operatorname{End}(E)$ has a root mod $\ell$.

That's just the existence question. We haven't even gotten to computation! Fortunately, if you understand all of the above theory, the computation part is relatively easy.

1. Solve the equation $\ell = x^2 + Dy^2$ for integers $x$ and $y$, using Cornacchia's algorithm.
2. Use Stark's algorithm to find the endomorphism $\phi$ corresponding to $\sqrt{-D}$. In the easy and fairly common case where $\sqrt{-D} = \pi_q$ ($q$-th power Frobenius map), you don't have to do anything here, since you already know how $\pi_q$ acts on $E$; you can just set $\phi = \pi_q$. EDIT #2: The previous sentence doesn't actually happen. What actually happens frequently is $\operatorname{End}(E) \cong \mathbb{Z}[\pi_q]$, in which case we have $\pi_q = (t + \sqrt{-D})/2$ by the characteristic equation of Frobenius. One can then easily solve for $\sqrt{-D}$ in terms of $\pi_q$ and the trace of Frobenius.
3. Now $x+y\phi$ and $x-y\phi$ are endomorphisms of $E$ of degree $\ell$. Done.