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