Cryptology ePrint Archive: Report 2007/253

Choosing the correct elliptic curve in the CM method

K. Rubin and A. Silverberg

Abstract: We give an elementary way to distinguish between the twists of an ordinary elliptic curve $E$ over $\Fp$ in order to identify the one with $p+1-2U$ points, when $p=U^2+\d V^2$ with $2U, 2V\in \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$.

Category / Keywords: implementation / elliptic curves, CM method, point-counting

Date: received 26 Jun 2007, last revised 20 Jan 2009

Contact author: asilverb at math uci edu

Available format(s): PDF | BibTeX Citation

Note: Minor changes from last version.

Version: 20090121:013955 (All versions of this report)

Short URL: ia.cr/2007/253

Discussion forum: Show discussion | Start new discussion