CryptoDB
Choosing the correct elliptic curve in the CM method
Authors: | |
---|---|
Download: | |
Abstract: | We give easy ways to distinguish between the twists of an ordinary elliptic curve $E$ over $\mathbb{F}_p$ in order to identify 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. This is useful for finding elliptic curves with a prescribed number of points, and is a new, faster, and easier way to implement the last step of the CM method. Our algorithms are completely elementary, in most cases consisting of merely reading off simple congruence conditions on $U$ and $V$ modulo $4$, whereas current algorithms rely on elliptic curve arithmetic and computing square roots. |
BibTeX
@misc{eprint-2007-13534, title={Choosing the correct elliptic curve in the CM method}, booktitle={IACR Eprint archive}, keywords={implementation / elliptic curves, CM method, point-counting}, url={http://eprint.iacr.org/2007/253}, note={ asilverb@math.uci.edu 13728 received 26 Jun 2007, last revised 3 Aug 2007}, author={K. Rubin and Alice Silverberg}, year=2007 }