Computing endomorphism rings of supersingular elliptic curves

Question

I would like to know what algorithms there are to compute the linearly independent generators $(1,i,j,k)$ for quaternion algebra containing the endomorphism ring of a supersingular curve. The curve in question is pretty small (around 16 bits, but I have no idea how to perform a brute force search).

One has that the Frobenius endomorphism would give us a generator linearly independent to the integers (that gives us $i^2=-p$), so how can one find the other? I have tried to look at Hilbert polynomials $h_D(X)$ for different $D$'s to see if $j_E$, the $j$-invariant of the elliptic curve, is a root, but there are more than one solution, so could one take the smallest $D$ so that $j^2=-D$?

Also, once the first part is completed, how does one find the $\mathbb{Z}$-basis that generates the endomorphism ring?

Lastly, how does one check if the endomorphism ring or the quaternion algebra obtained from the algorithms are correct?

(Aside: Does anyone have a reference to show that roots of $D$-Hilbert polynomials are $j$-invariants of elliptic curves with endomorphism ring containing the imaginary quadratic field with discriminant $D$? I've seen it used all the time, but have not seen an explicit reference.)

Edit: I have found a paper by Pizer that contains a proposition (5.1) that describes the quaternion algebra the endomorphism ring lives in. Another proposition (5.2) describes a maximal order, but this still does not help my cause.

Answer 1

Let me give a very partial answer, in line with my comment. If $y^2=x^3+1$ is supersingular, i.e. $p\equiv5\pmod6$, then the cube roots of unity are not in the prime field, so that the automorphism $(x,y)\mapsto(\omega x,y)$ does not commute with Frobenius $(x,y)\mapsto(x^p,y^p)$.

Similarly, if $y^2=x^3-x$ is supersingular, i.e. $p\equiv3\pmod4$, then the fourth roots of unity are not in the prime field, and the automorphism $(x,y)\mapsto(-x,iy)$ does not commute with Frobenius.

I’m sure that in each case, the four endomorphisms you see form a $\Bbb Q$-basis for $\Bbb Q\otimes_{\Bbb Z}\mathrm{End}$, and it looks to me as if they ought to form a $\Bbb Z$-basis for the endomorphism ring itself.

I don’t know how to handle primes that are $\equiv1\pmod{12}$ (nor any supersingular values different from $0$ and $1728$).

Answer 2

For the computation of a basis of the endomorphism algebra, you should read David Kohel's thesis, see for instance Theorem 2.

To find the endomorphism ring, you can repeat Kohel's methods to find more endomorphisms, until the ring they generate is a maximal order in the algebra.

In order to check that the endomorphism algebra is correct, you only need to check that the basis elements really are endomorphisms and that they generate an algebra of dimension $4$. If you are only given the isomorphism class (and not actual endomorphisms), you need to check that the algebra is ramified exactly at $\{p,\infty\}$. Similarly, to check that the endomorphism ring is correct, you only need to check that you are given actual endomorphisms and that they generate a maximal order in a quaternion algebra. If you are only given the isomorphism class, I don't know how to check that it is correct faster than by recomputing it and comparing the results.

For more about quaternion algebras and how to algorithmically perform the tasks I mentionned, see John Voight's book and references therein.