Constructing supersingular elliptic curves with a given endomorphism
ring

Let O be a maximal order in the quaternion algebra B_p over Q ramified at p
and infinity. The paper is about the computational problem: Construct a
supersingular elliptic curve E over F_p such that End(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 O^T of O, the order O is effectively
characterized by the three successive minima and two other short vectors of
O^T. The desired conditions turn out to hold whenever the j-invariant j(E), of
the elliptic curve with End(E) = O, lies in F_p. We can then prove that our
algorithm terminates with running time O(p^{1+\epsilon}) 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(p^{2.5+\epsilon}) operations and
is more efficient than Cervino's algorithm for the same problem.