International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Choosing the correct elliptic curve in the CM method

Authors:
K. Rubin
Alice Silverberg
Download:
URL: http://eprint.iacr.org/2007/253
Search ePrint
Search Google
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
}