Constructing supersingular elliptic curves with a given endomorphism ring

Ilya Chevyrev, Steven D. Galbraith

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

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.
Original languageEnglish
Pages (from-to)71-91
Number of pages20
JournalLMS Journal of Computation and Mathematics
Volume17
Issue numberA
Early online date1 Aug 2014
DOIs
Publication statusPublished - 31 Dec 2014
EventAlgorithmic Number Theory Symposium (ANTS XI) - Gyeongju, Korea, Republic of
Duration: 7 Aug 201411 Aug 2014

Fingerprint

Dive into the research topics of 'Constructing supersingular elliptic curves with a given endomorphism ring'. Together they form a unique fingerprint.

Cite this