Computing the cardinality of CM elliptic curves using torsion points

Let ℰ / ℚ ¯ be an elliptic curve having complex multiplication by a given quadratic order of an imaginary quadratic field 𝕂 . The field of definition of ℰ is the ring class field Ω of the order. If the prime p splits completely in Ω , then we can reduce ℰ modulo one the factors of p and get a curve E defined over 𝔽 p . The trace of the Frobenius of E is known up to sign and we need a fast way to find this sign, in the context of the Elliptic Curve Primality Proving algorithm (ECPP). For this purpose, we propose to use the action of the Frobenius on torsion points of small order built with class invariants generalizing the classical Weber functions.