Accelerating the CM method
From MaRDI portal
Publication:5169634
Abstract: Given a prime q and a negative discriminant D, the CM method constructs an elliptic curve E/Fq by obtaining a root of the Hilbert class polynomial H_D(X) modulo q. We consider an approach based on a decomposition of the ring class field defined by H_D, which we adapt to a CRT setting. This yields two algorithms, each of which obtains a root of H_D mod q without necessarily computing any of its coefficients. Heuristically, our approach uses asymptotically less time and space than the standard CM method for almost all D. Under the GRH, and reasonable assumptions about the size of log q relative to |D|, we achieve a space complexity of O((m+n)log q) bits, where mn=h(D), which may be as small as O(|D|^(1/4)log q). The practical efficiency of the algorithms is demonstrated using |D| > 10^16 and q ~ 2^256, and also |D| > 10^15 and q ~ 2^33220. These examples are both an order of magnitude larger than the best previous results obtained with the CM method.
Recommendations
- Accelerated method of conjugate gradients
- scientific article; zbMATH DE number 4028771
- scientific article; zbMATH DE number 5012790
- scientific article; zbMATH DE number 4161339
- Chebyshev acceleration of the method of Cimmino
- Acceleration methods based on convergence tests
- scientific article; zbMATH DE number 434532
- Convergence acceleration of Kaczmarz's method
- Acceleration schemes for the method of alternating projections
- Sélection entre procédés d'accélération de la convergence
Cites work
- A p-adic algorithm to compute the Hilbert class polynomial
- A cache-friendly truncated FFT
- Binary quadratic forms. An algorithmic approach
- Choosing the correct elliptic curve in the CM method
- Class invariants by the CRT method
- Computing Hilbert Class Polynomials
- Computing Hilbert class polynomials with the Chinese remainder theorem
- Computing the endomorphism ring of an ordinary elliptic curve over a finite field
- Fast Decomposition of Polynomials with Known Galois Group
- Fast multiplication of large numbers
- scientific article; zbMATH DE number 3657869 (Why is no real title available?)
- scientific article; zbMATH DE number 2206373 (Why is no real title available?)
- Modular exponentiation via the explicit Chinese remainder theorem
- Modular polynomials via isogeny volcanoes
- ON PRIMES IN QUADRATIC PROGRESSIONS
- Pairing the volcano
- PRIMES is in P
- Structure computation and discrete logarithms in finite abelian \(p\)-groups
- The complexity of class polynomial computation via floating point approximations
Cited in
(26)- Gross-Zagier type CM value formulas on X₀^(p)
- Quantum lattice enumeration and tweaking discrete pruning
- Scalable zero knowledge via cycles of elliptic curves
- Towards practical key exchange from ordinary isogeny graphs
- Generalized class polynomials
- Cocks-Pinch curves of embedding degrees five to eight and optimal ate pairing computation
- Revisiting the complex multiplication method for the construction of elliptic curves
- The complexity of class polynomial computation via floating point approximations
- Computing Hilbert class polynomials with the Chinese remainder theorem
- Finding elliptic curves with a subgroup of prescribed size
- Efficient CM-constructions of elliptic curves over finite fields
- scientific article; zbMATH DE number 641617 (Why is no real title available?)
- scientific article; zbMATH DE number 2154267 (Why is no real title available?)
- Class invariants by the CRT method
- Genus-2 curves and Jacobians with a given number of points
- A Method for Distinguishing the Two Candidate Elliptic Curves in CM Method
- Character sums and deterministic polynomial root finding in finite fields
- On Cycles of Pairing-Friendly Elliptic Curves
- Constructing Picard curves with complex multiplication using the Chinese remainder theorem
- Revisiting cycles of pairing-friendly elliptic curves
- Computing classical modular forms
- Climbing and descending tall isogeny volcanos
- Isogeny graphs of ordinary abelian varieties
- Schertz style class invariants for higher degree CM fields
- Cycles of supersingular elliptic curves for pairing-based proof systems
- Ramanujan's class invariants and their use in elliptic curve cryptography
This page was built for publication: Accelerating the CM method
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5169634)
