Hostname: page-component-7b7567c8c-fvjsw Total loading time: 0 Render date: 2026-11-16T06:53:11.413Z Has data issue: false hasContentIssue false

Constructing supersingular elliptic curves with a given endomorphism ring

Published online by Cambridge University Press:  01 August 2014

Ilya Chevyrev
Affiliation:
Mathematical Institute, University of Oxford, United Kingdom email ilya.chevyrev@maths.ox.ac.uk
Steven D. Galbraith
Affiliation:
Mathematics Department, University of Auckland, New Zealand email S.Galbraith@math.auckland.ac.nz

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Let $\def \xmlpi #1{}\def \mathsfbi #1{\boldsymbol {\mathsf {#1}}}\let \le =\leqslant \let \leq =\leqslant \let \ge =\geqslant \let \geq =\geqslant \def \Pr {\mathit {Pr}}\def \Fr {\mathit {Fr}}\def \Rey {\mathit {Re}}\mathcal{O}$ be a maximal order in the quaternion algebra $B_p$ over $\mathbb{Q}$ ramified at $p$ and $\infty $. The paper is about the computational problem: construct a supersingular elliptic curve $E$ over $\mathbb{F}_p$ such that ${\rm End}(E) \cong \mathcal{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 $\mathcal{O}^T$ of $\mathcal{O}$, the order $\mathcal{O}$ is effectively characterized by the three successive minima and two other short vectors of $\mathcal{O}^T\! .$ The desired conditions turn out to hold whenever the $j$-invariant $j(E)$, of the elliptic curve with ${\rm End}(E) \cong \mathcal{O}$, lies in $\mathbb{F}_p$. We can then prove that our algorithm terminates with running time $O(p^{1+\varepsilon })$ 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 + \varepsilon })$ operations and is more efficient than Cerviño’s algorithm for the same problem.