Computing Hilbert class polynomials with the Chinese remainder theorem

DOI10.1090/S0025-5718-2010-02373-7zbMath1231.11144arXiv0903.2785MaRDI QIDQ3081296

Andrew V. Sutherland

Publication date: 7 March 2011

Published in: Mathematics of Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/0903.2785

zbMATH Keywords

Hilbert class polynomialnegative discriminant

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Elliptic curves (14H52) Curves over finite and local fields (11G20) Complex multiplication and moduli of abelian varieties (11G15)

Related Items (40)

Improved supersingularity testing of elliptic curves using Legendre form ⋮ Gross-Zagier type CM value formulas on \(X_0^\ast(p)\) ⋮ Finding elliptic curves with a subgroup of prescribed size ⋮ Generating pairing-friendly elliptic curve parameters using sparse families ⋮ A quasi-linear time algorithm for computing modular polynomials in dimension 2 ⋮ Distorting the volcano ⋮ Hilbert modular polynomials ⋮ -adic images of Galois for elliptic curves over (and an appendix with John Voight) ⋮ A survey of elliptic curves for proof systems ⋮ Computing the endomorphism ring of an ordinary abelian surface over a finite field ⋮ Scalable zero knowledge via cycles of elliptic curves ⋮ On the distribution of Atkin and Elkies primes ⋮ Computational Number Theory, Past, Present, and Future ⋮ Class polynomials for nonholomorphic modular functions ⋮ Lower bounds on the maximal number of rational points on curves over finite fields ⋮ Degree and height estimates for modular equations on PEL Shimura varieties ⋮ Simple and exact formula for minimum loop length in \(\mathrm{Ate}_{i }\) pairing based on Brezing-Weng curves ⋮ Computing isogeny volcanoes of composite degree ⋮ Computing the endomorphism ring of an ordinary elliptic curve over a finite field ⋮ Finding composite order ordinary elliptic curves using the Cocks-Pinch method ⋮ Heuristics of the Cocks-Pinch method ⋮ On the number of isogeny classes of pairing-friendly elliptic curves and statistics of MNT curves ⋮ Constructing elliptic curves over finite fields with prescribed torsion ⋮ Modular polynomials via isogeny volcanoes ⋮ Isogeny graphs of ordinary abelian varieties ⋮ Accelerating the CM method ⋮ Identifying supersingular elliptic curves ⋮ Computing separable isogenies in quasi-optimal time ⋮ A taxonomy of pairing-friendly elliptic curves ⋮ Analogues of Vélu’s formulas for isogenies on alternate models of elliptic curves ⋮ A cache-friendly truncated FFT ⋮ Character sums and deterministic polynomial root finding in finite fields ⋮ Modular polynomials on Hilbert surfaces ⋮ Improved supersingularity testing of elliptic curves ⋮ Computing $(\ell ,\ell )$-isogenies in polynomial time on Jacobians of genus $2$ curves ⋮ Computing endomorphism rings of abelian varieties of dimension two ⋮ Supersingular curves with small noninteger endomorphisms ⋮ Generalized class polynomials ⋮ Supersingular j-invariants and the class number of ℚ(−p) ⋮ Spanning the isogeny class of a power of an elliptic curve

Uses Software

• gmp
• ECPP

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On a theorem of Mestre and Schoof
• Faster polynomial multiplication via multipoint Kronecker substitution
• Binary quadratic forms. An algorithmic approach
• Factoring integers with elliptic curves
• A taxonomy of pairing-friendly elliptic curves
• The distribution of group structures on elliptic curves over finite prime fields
• Computing the endomorphism ring of an ordinary elliptic curve over a finite field
• Computing the height of volcanoes of \(\ell \)-isogenies of elliptic curves over finite fields
• Fast multiplication of large numbers
• Approximate formulas for some functions of prime numbers
• Die Typen der Multiplikatorenringe elliptischer Funktionenkörper
• A $p$-adic algorithm to compute the Hilbert class polynomial
• The complexity of class polynomial computation via floating point approximations
• Computing modular polynomials in quasi-linear time
• Elliptic Curves and Primality Proving
• On the coefficients of the transformation polynomials for the elliptic modular function
• Modular exponentiation via the explicit Chinese remainder theorem
• Explicit Bounds for Primality Testing and Related Problems
• A Rigorous Subexponential Algorithm For Computation of Class Groups
• On Prime-Order Elliptic Curves with Embedding Degrees k = 3, 4, and 6
• Choosing the correct elliptic curve in the CM method
• Efficient CM-constructions of elliptic curves over finite fields
• Constructing Brezing-Weng Pairing-Friendly Elliptic Curves Using Elements in the Cyclotomic Field
• Universal Bounds on the Torsion of Elliptic Curves
• A space efficient algorithm for group structure computation
• Finding Suitable Curves for the Elliptic Curve Method of Factorization
• Determining the $2$-Sylow subgroup of an elliptic curve over a finite field
• Computing the structure of a finite abelian group
• Handbook of Elliptic and Hyperelliptic Curve Cryptography
• Computing Hilbert Class Polynomials
• Computing L-Series of Hyperelliptic Curves
• On the arithmetic of certain modular curves
• Algorithmic Number Theory
• Algorithmic Number Theory

This page was built for publication: Computing Hilbert class polynomials with the Chinese remainder theorem