Choosing the correct elliptic curve in the CM method
Karl Rubin, Alice Silverberg · Mathematics of Computation · 2009
We give an elementary way to distinguish between the twists of an ordinary elliptic curve $E$ over $\mathbb {F}_p$ in order to identify the one with $p+1-2U$ points, when $p=U^2+dV^2$ with $2U, 2V\in \mathbb {Z}$ and $E$ is constructed using the CM method for finding elliptic curves with a prescribed number of points. Our algorithms consist in most cases of reading off simple congruence conditions on $U$ and $V$ modulo $4$.