Computing the trace of a supersingular endomorphism

For an elliptic curve E, Schoof’s algorithm computes the number of points of an elliptic curve over a finite field by computing the trace of the Frobenius endomorphism modulo enough primes in order to recover the trace via the CRT. Elkies’ improvement to Schoof’s algorithm involves computing the trace of Frobenius modulo primes ell for which E has a rational ell isogeny; asymptotically, such primes account for 50% of all primes. In practice, this gives a substantial speedup over Schoof’s algorithm, but heuristics beyond GRH are required to prove that it yields an asymptotic speedup. Computing the trace of an arbitrary endomorphism can be done with a generalization of Schoof’s algorithm. When E is supersingular, computing the trace of an endomorphism is an important subroutine in various algorithms for computing the endomorphism ring of E. And in the supersingular case, assuming E is defined over the finite field of p^{2} elements, E always has rational ell-isogenies – we leverage this in a generalization of the SEA algorithm for supersingular endomorphisms, yielding an asymptotic speedup over the generalization of Schoof’s algorithm, conditional only on GRH. We gain further speedups in practice: for example, we can compute the trace modulo p (the characteristic) by computing the action on an invariant differential of E, and we can leverage knowledge of the number of points of E since E is supersingular to compute the trace modulo primes dividing p+/- 1. This is joint work with Lorenz Panny, Jana Sotakova, and Michael Wills.