The complexity of class polynomial computation via floating point approximations

DOI10.1090/S0025-5718-08-02200-XzbMath1208.11136OpenAlexW2026644646MaRDI QIDQ3055132

Andreas Enge

Publication date: 7 November 2010

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

Full work available at URL: https://doi.org/10.1090/s0025-5718-08-02200-x

zbMATH Keywords

elliptic curvesmodular functionsclass numbercomplex multiplicationclass polynomialsfloating point

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Complex multiplication and moduli of abelian varieties (11G15)

Related Items

Isogenous hyperelliptic and non-hyperelliptic Jacobians with maximal complex multiplication, Constructing irreducible polynomials over finite fields, Gross-Zagier type CM value formulas on \(X_0^\ast(p)\), Finding elliptic curves with a subgroup of prescribed size, Class polynomials for nonholomorphic modular functions, Certified Newton schemes for the evaluation of low-genus theta functions, On the evaluation of some sparse polynomials, Computing Jacobi’s theta in quasi-linear time, Computing theta functions in quasi-linear time in genus two and above, Computing Hilbert Class Polynomials, Modular polynomials via isogeny volcanoes, Fast evaluation of modular functions using Newton iterations and the AGM, FINDING SINGULAR MODULI ON A COMPLEX LINE, Accelerating the CM method, Choosing the correct elliptic curve in the CM method, A taxonomy of pairing-friendly elliptic curves, A $p$-adic algorithm to compute the Hilbert class polynomial, Computing modular polynomials in quasi-linear time, Computing Hilbert class polynomials with the Chinese remainder theorem, Expander graphs based on GRH with an application to elliptic curve cryptography, Short addition sequences for theta functions, Unnamed Item, Implementing the asymptotically fast version of the elliptic curve primality proving algorithm, Computing Igusa class polynomials, Generalized class polynomials, Spanning the isogeny class of a power of an elliptic curve, Generalised Weber functions, Computing Class Polynomials for Abelian Surfaces

Uses Software

• gmp
• MPFR
• ECPP
• MPC

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
• Building curves with arbitrary small MOV degree over finite prime fields
• Weber's class invariants revisited
• Class invariants by Shimura's reciprocity law
• Computing Frobenius maps and factoring polynomials
• Constructing elliptic curves over finite fields using double eta-quotients
• Fast multiplication of large numbers
• Elliptic curves suitable for pairing based cryptography
• Die Typen der Multiplikatorenringe elliptischer Funktionenkörper
• Fast evaluation of modular functions using Newton iterations and the AGM
• Elliptic Curves and Primality Proving
• Explicit Bounds for Primality Testing and Related Problems
• Constructing elliptic curves of prime order
• MPFR
• Fast Multiple-Precision Evaluation of Elementary Functions
• Die singulären Werte der Weberschen Funktionen f, f1, f2, 2, 3.
• Prime sieves using binary quadratic forms
• Über die Classenzahl quadratischer Zahlkörper
• Elliptic Curves with a Given Number of Points