Accelerating the CM method

DOI10.1112/S1461157012001015zbMath1343.11098arXiv1009.1082MaRDI QIDQ5169634

Andrew V. Sutherland

Publication date: 11 July 2014

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

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

Mathematics Subject Classification ID

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

Related Items

Gross-Zagier type CM value formulas on \(X_0^\ast(p)\), Quantum lattice enumeration and tweaking discrete pruning, Finding elliptic curves with a subgroup of prescribed size, Cocks-Pinch curves of embedding degrees five to eight and optimal ate pairing computation, Scalable zero knowledge via cycles of elliptic curves, Constructing Picard curves with complex multiplication using the Chinese remainder theorem, Revisiting cycles of pairing-friendly elliptic curves, Towards practical key exchange from ordinary isogeny graphs, Isogeny graphs of ordinary abelian varieties, Genus-2 curves and Jacobians with a given number of points, On Cycles of Pairing-Friendly Elliptic Curves, Character sums and deterministic polynomial root finding in finite fields, Generalized class polynomials

Uses Software

• zn_poly

Cites Work

• Unnamed Item
• Unnamed Item
• Binary quadratic forms. An algorithmic approach
• A cache-friendly truncated FFT
• PRIMES is in P
• Computing the endomorphism ring of an ordinary elliptic curve over a finite field
• Fast multiplication of large numbers
• A $p$-adic algorithm to compute the Hilbert class polynomial
• The complexity of class polynomial computation via floating point approximations
• Structure computation and discrete logarithms in finite abelian $p$-groups
• Computing Hilbert class polynomials with the Chinese remainder theorem
• Modular exponentiation via the explicit Chinese remainder theorem
• Choosing the correct elliptic curve in the CM method
• ON PRIMES IN QUADRATIC PROGRESSIONS
• Fast Decomposition of Polynomials with Known Galois Group
• Class Invariants by the CRT Method
• Pairing the Volcano
• Computing Hilbert Class Polynomials
• Modular polynomials via isogeny volcanoes