paper

Constructing supersingular elliptic curves with a given endomorphism ring

arXiv:1301.6875 · doi:10.1112/S1461157014000254

Abstract

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+ε}) 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+ε}) operations and is more efficient than Cervino's algorithm for the same problem.

arXiv commentFull version of paper published by the LMS Journal of Computation and Mathematics

References in corpus (1)

Cited by in corpus (1)