Visual Arts

Computing Hilbert Class Polynomials
1 2 3 2Juliana Belding , Reinier Br¨oker , Andreas Enge , Kristin Lauter
1 Dept. of Mathematics, University of Maryland, College Park, MD 20742, USA
2 Microsoft Research, One Microsoft Way, Redmond, WA 98052, USA
3 ´INRIA Futurs & Laboratoire d’Informatique (CNRS/UMR 7161), Ecole
polytechnique, 91128 Palaiseau cedex, France
jbelding@math.umd.edu reinierb@microsoft.com enge@lix.polytechnique.fr
klauter@microsoft.com
Abstract. We present and analyze two algorithms for computing the
Hilbert class polynomial H . The first is a p-adic lifting algorithm forD
inert primesp in the order of discriminantD< 0. The second is an im-
provedChineseremainderalgorithmwhichusestheclassgroupactionon
CM-curves over finite fields. Our run time analysis gives tighter bounds
for the complexity of all known algorithms for computing H , and weD
show that all methods have comparable run times.
1 Introduction
ForanimaginaryquadraticorderO =O ofdiscriminantD < 0,thej-invariantD
ofthecomplexellipticcurveC/O isanalgebraicinteger.Itsminimalpolynomial
H ∈ Z[X] is called the Hilbert class polynomial. It defines the ring class fieldD
K corresponding to O, and within the context of explicit class field theory, itO
is natural to ask for an algorithm to explicitly compute H .D
Algorithms to compute H are also interesting for elliptic curve primalityD
proving [2] and for cryptographic purposes [5]; for instance, pairing-based cryp-
tosystems using ordinary curves rely on complex multiplication techniques to
generatethecurves.TheclassicalapproachtocomputeH istoapproximatetheD
valuesj(τ )∈Cofthecomplexanalyticj-functionatpointsτ intheupperhalfa a
plane corresponding to the ideal classes a for the order O. The polynomial HDQ
mayberecoveredbyroundingthecoefficientsof (X−j(τ ))∈C[X]toaa∈Cl(O)
the nearest integer. It is shown in [8] that an optimized version of that algorithm
has a complexity that is essentially linear in the output size.
Alternatively one can compute H using a p-adic lifting algorithm [6,3].D
Here, the prime p splits completely in K and is therefore relatively large: itO
satisfies the lower bound p ≥ |D|/4. In this paper we give a p-adic algorithm
for inert primes p. Such primes are typically much smaller than totally split
2primes, and under GRH there exists an inert prime of size only O((log|D|) ).
The complex multiplication theory underlying all methods is more intricate for
inertprimesp,astherootsofH ∈F 2[X]arenowj-invariantsof supersingularD p
elliptic curves. In Section 2 we explain how to define the canonical lift of asupersingular elliptic curve, and in Section 4 we describe a method to explicitly
compute this lift.
In another direction, it was suggested in [1] to compute H modulo severalD
totally split primes p and then combine the information modulo p using the
Chinese remainder theorem to compute H ∈ Z[X]. The first version of thisD
algorithm was quite impractical, and in Section 3 we improve this ‘multi-prime
approach’ in two different ways. We show how to incorporate inert primes, and
we improve the original approach for totally split primes using the class group
action on CM-curves. We analyze the run time of the new algorithm in Section 5
in terms of the logarithmic height ofH , its degree, the largest prime needed toD
generate the class group ofO and the discriminant D. Our tight bounds on the
first two quantities from Lemmata 1 and 2 apply to all methods to computeH .D
For the multi-prime approach, we derive the following result.
Theorem 1. The algorithm presented in Section 3 computes, for a discriminant
D < 0, the Hilbert class polynomial H . If GRH holds true, the algorithm hasD
7+o(1)an expected run time O |D|(log|D|) . Under heuristic assumptions, the

3+o(1)complexity becomes O |D|(log|D|) .
We conclude by giving examples of the presented algorithms in Section 6.
2 Complex multiplication in characteristic p
Throughout this section, D < −4 is any discriminant, and we write O for the
imaginary quadratic order of discriminant D. Let E/K be an elliptic curveO
with endomorphism ring isomorphic toO. AsO has rank 2 as aZ-algebra, there
∼
are two isomorphisms ϕ : End(E)−→O. We always assume we have chosen the
∗normalized isomorphism,i.e.,forally∈O wehaveϕ(y) ω =yω forallinvariant
differentials ω. For ease of notation, we write E for such a ‘normalized elliptic
curve,’ the isomorphism ϕ being understood.
For a field F, let Ell (F) be the set of isomorphism classes of elliptic curvesD
over F with endomorphism ringO. The ideal group ofO acts on Ell (K ) viaD O
a
j(E)7→j(E) =j(E/E[a]),
where E[a] is the group of a-torsion points, i.e., the points that are annihilated
by all α∈ a⊂O = End(E). As principal ideals act trivially, this action factors
through the class group Cl(O). The Cl(O)-action is transitive and free, and
Ell (K ) is a principal homogeneous Cl(O)-space.D O
Let p be a prime that splits completely in the ring class field K . We canO
embed K in the p-adic field Q , and the reduction map Z → F induces aO p p p
bijection Ell (Q )→ Ell (F ). The Cl(O)-action respects reduction modulo p,D p D p
and the set Ell (F ) is a Cl(O)-torsor, just like in characteristic zero. This ob-D p
servationisofkeyimportancefortheimproved‘multi-prime’approachexplained
in Section 3.
We now consider a prime p that is inert inO, fixed for the remainder of this
section. As the principal prime (p) ⊂ O splits completely in K , all primes ofOK lying over p have residue class degree 2. We view K as a subfield of theO O
unramified degree 2 extension L of Q . It is a classical result, see [7] or [13,p
Th. 13.12], that for [E] ∈ Ell (L), the reduction E is supersingular. It canD p
be defined over the finite field F 2, and its endomorphism ring is a maximalp
order in the unique quaternion algebraA which is ramified at p and∞. Thep,∞
reduction map Z → F 2 also induces an embedding f : O ,→ End(E ). ThisL p p
embedding is not surjective, as it is in the split case, since End(E ) has rank 4p
as a Z-algebra, andO has rank 2.
We let Emb (F 2) be the set of isomorphism classes of pairs (E ,f) withD pp
E /F 2 asupersingularellipticcurveandf :O→ End(E )anembedding.Here,p pp
∼0 0 0(E ,f) and (E ,f ) are isomorphic if there exists an isomorphismh :E −→Ep pp p
−1 0ofellipticcurveswithh f (α)h =f(α)forallα∈O.Asanalogueofpickingthe
∼
normalized isomorphism O −→ End(E) in characteristic zero, we now identify
0 0 0(E ,f) and (E ,f ) if f equals the complex conjugate of f .p p
Theorem 2. Let D < −4 be a discriminant. If p is inert in O = O , the re-D
duction map π : Ell (L)→ Emb (F 2) is a bijection. Here, L is the unramifiedD D p
extension of Q of degree 2.p
Proof. By the Deuring lifting theorem, see [7] or [13, Th. 13.14], we can lift an
element of Emb (F 2) to an element of Ell (L). Hence, the map is surjective.D Dp
0 0Suppose that we have π(E) =π(E ). As E and E both have endomorphism
a 0ring O, they are isogenous. We let ϕ : E → E = E be an isogeny. We havea
0 af =f , and withO =Z[τ], we get
a −1bf :τ 7→ϕ f(τ)ϕ ⊗(degϕ ) ∈ End(E )⊗Q.pa a a
Weseethatϕ iscontainedinS =f(End(E))⊗Q,sinceitcommuteswithf(τ).a
0 0Write O = S∩End(E ), and let m be the index [O : f(End(E))]. For anyp
0δ ∈ O , there exists γ ∈ End(E) with mδ = f(γ). As f(γ) annihilates the m-
torsion E [m], γ annihilates E[m], thus it is a multiple of m inside End(E). Wep
0derive that δ is contained in f(End(E)), and O = f(End(E)). Hence, ϕ is ana
aendomorphism of E, and E and E are isomorphic.
e 2The canonical lift E of a pair (E ,f) ∈ Emb (F ) is defined as the inversep D p
−1π (E ,f)∈ Ell (L). This generalizes the notion of a canonical lift for ordinaryp D
ellipticcurves,andthemainstepofthep-adicalgorithmdescribedinSection4is
etocomputeE:itsj-invariantisazerooftheHilbertclasspolynomialH ∈L[X].D
The reduction map Ell (L) → Emb (F 2) induces a transitive and freeD D p
action of the class group on the set Emb (F 2). For an O-ideal a, let ϕ :D p a
aE → E be the isogeny of CM-curves with kernel E[a]. Writing O = Z[τ], let
∼
β∈ End(E)betheimageofτ underthenormalizedisomorphismO−→End(E).
aThe normalized isomorphism for E is now given by
−1τ 7→ϕ βϕb ⊗(degϕ ) .a a a
∼a a a a aWe have E = (E ) and f is the composition O −→ End(E ) ,→ End(E ).pp p
Note that principal ideals indeed act trivially: ϕ is an endomorphism in thisa
acase and, as End(E) is commutative, we have f =f .To explicitly compute this action, we fix one supersingular curve E /F 2p p
∼
and an isomorphism i : A −→ End(E )⊗Q and view the embedding fE p,∞ pp
−1as an injective map f : O ,→ A . Let R = i (End(E )) be the maximalp,∞ pEp
order of A corresponding to E . For a an ideal of O, we compute the curvep,∞ p
a aE = ϕ (E ) and choose an auxiliary isogeny ϕ : E → E . This induces anp b pp a p
∼ aisomorphism g :A −→ End(E )⊗Q given byb p,∞ p
−1
α7→ϕ i (α)ϕb ⊗(degϕ ) .b E b bp
The left R-ideals Rf(a) and b are left-isomorphic by [21, Th. 3.11] and thus we
can find x ∈ A with Rf(a) = bx. As y = f(τ) is an element of Rf(a), wep,∞
−1get the embeddingτ 7→xyx into the right orderR of b. By construction, theb
a ainduced embedding f :O ,→ End(E ) is preciselyp
a −1 a
f (τ) =g (xyx )∈ End(E ),b p
aandthisisindependentofthechoiceof b.Forexample,ifE =E ,thenchoosingpp
aϕ as the identity, we find x with Rf(a) = Rx to get the embedding f :