15
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ Is your question about a specific curve, in a specific characteristic? $\endgroup$
    – Lubin
    Commented May 9, 2016 at 15:25
  • $\begingroup$ @Lubin Sorry for the late reply! I would like to know if it is possible to do this in general, however, if there are specific cases where it is easier (maybe when $j=0$ or $1728$), I'll be interested to know! $\endgroup$
    – BlackAdder
    Commented May 16, 2016 at 21:59
  • $\begingroup$ I've done it for the case of char two, five rational points over the prime field. Had to go to the field with sixteen elements to catch the whole ring. When your curve has obvious periodic automs, it's easy enough to get four indep. endoms, but I would never claim I had the whole ring. $\endgroup$
    – Lubin
    Commented May 16, 2016 at 23:24
  • $\begingroup$ @Lubin Thanks for your comments. Could you explain how the presence of periodic automorphisms can help someone to find the independent endomorphisms? I can't quite see it. What I had in mind that in $j=0$ or $1728$, we endo. of small norm which might make it easy to recover the indep. endo. $\endgroup$
    – BlackAdder
    Commented May 17, 2016 at 22:28

2 Answers 2

Reset to default
4
$\begingroup$

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$).

Improve this answer
$\endgroup$
1
  • $\begingroup$ For $y^2 = x^3-x$ and $p \equiv 3 \pmod 4$, the $2$-torsion is defined over $\Bbb F_p$, i.e. $\ker([2]) \subset \ker(Fr_p - 1)$, so $2 \mid (Fr_p -1)$ or equivalently $2 \mid (Fr_p +1)$, thus $(1+Fr_p)/2$ belongs to the endomorphism ring as well. $\endgroup$
    – Watson
    Commented Mar 25, 2020 at 16:22
3
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ hi, I was trying to implement this on SAGE. I honestly couldn't understand how exactly Kohel's thesis deal with the following? (1) How are endomorphism being represented and sampled? (2) How to check the rank of endomorphisms? (3) How to check the algebra ramifies at {p,inf}? (4) How to check an endomorphism generates an maximal ideal? I checked out the Chapter 7 but just couldn't make any such connection. $\endgroup$
    – Taylor Huang
    Commented Apr 6, 2020 at 9:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .