2002/10/11 by François Morain, F. Morain, Morain, F.
Computer Science · Engineering · Mathematics · #11G15 #11G20 #Advanced Numerical Analysis Techniques #Algebraic Geometry and Number Theory #Cryptography and Residue Arithmetic #FOS: Mathematics #Number Theory (math.NT) #math.NT #msc:11G15 #msc:11G20
paper · pdf · doi:10.48550/arxiv.math/0210173
Revised and shortened version, including more material using discriminants of curves and division polynomials
openalex publication_date 2002/10/11 · arxiv created 2004/07/23 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let E be an elliptic curve having complex multiplication by a given quadratic order of an imaginary quadratic field K. The field of definition of E is the ring class field Omega of the order. If the prime p splits completely in Omega, then we can reduce E modulo one the factors of p and get a curve Ep defined over GF(p). The trace of the Frobenius of Ep is known up to sign and we need a fast way to find this sign. For this, we propose to use the action of the Frobenius on torsion points of small order built with class invariants a la Weber, in a manner reminiscent of the Schoof-Elkies-Atkin algorithm for computing the cardinality of a given elliptic curve modulo p. We apply our results to the Elliptic Curve Primality Proving algorithm (ECPP).