Constructing supersingular elliptic curves with a given endomorphism ring

Let O be a maximal order in the quaternion algebra Bp over Q ramified at p and ∞. The paper is about the computational problem: construct a supersingular elliptic curve E over Fp such that (E) ≅ O. We present an algorithm that solves this problem by taking gcds of the reductions modulo p of Hilbert class polynomials. New theoretical results are required to determine the complexity of our algorithm. Our main result is that, under certain conditions on a rank three sublattice OT of O, the order O is effectively characterized by the three successive minima and two other short vectors of OT. The desired conditions turn out to hold whenever the j-invariant j(E), of the elliptic curve with { End}(E) ≅ O, lies in Fp. We can then prove that our algorithm terminates with running time O(p1+ε) under the aforementioned conditions. As a further application we present an algorithm to simultaneously match all maximal order types with their associated j-invariants. Our algorithm has running time O(p2.5 + ε) operations and is more efficient than Cerviño's algorithm for the same problem. © 2014 The Author(s).