Visual Arts
14 pages
English

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Visual Arts

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus
14 pages
English
Obtenez un accès à la bibliothèque pour le consulter en ligne
En savoir plus

Description

  • mémoire
  • mémoire - matière potentielle : drawings
  • expression écrite - matière potentielle : a recount for the class as a joint construction
  • leçon - matière potentielle : forms
Early Stage 1 — About Me Subject Matter: People Unit Duration: 4–6 lessons Forms: Drawing, Painting In this unit, students explore their uniqueness and individuality in their making of artworks and recognise that other artists think about the uniqueness of people when they make portraits of them. Students will make self portraits developing their observational skills and considering the qualities and relationships between features and how these are represented in their picture making.
  • favourite works within the class group
  • black textas
  • life-size black
  • significant events
  • artworks
  • face
  • fireworks
  • students
  • -1 unit
  • unit
  • work

Sujets

Informations

Publié par
Nombre de lectures 17
Langue English

Extrait

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 :

  • Univers Univers
  • Ebooks Ebooks
  • Livres audio Livres audio
  • Presse Presse
  • Podcasts Podcasts
  • BD BD
  • Documents Documents