Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Choosing the correct elliptic curve in the CM method


Authors: K. Rubin and A. Silverberg
Journal: Math. Comp. 79 (2010), 545-561
MSC (2000): Primary 11Y40, 11G20, 11T71, 11G15
DOI: https://doi.org/10.1090/S0025-5718-09-02266-2
Published electronically: July 13, 2009
MathSciNet review: 2552240
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: 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$.


References [Enhancements On Off] (What's this?)

  • 1. A. O. L. Atkin, F. Morain, Elliptic curves and primality proving, Math. Comp. 61 (1993), 29-68. MR 1199989 (93m:11136)
  • 2. J. Belding, R. Bröker, A. Enge, K. Lauter, Computing Hilbert class polynomials, in Algorithmic number theory -- ANTS-VIII, Lecture Notes in Comput. Sci. 5011, Springer, Berlin, 2008, 282-295. MR 2467854
  • 3. B. J. Birch, Weber's class invariants, Mathematika 16 (1969), 283-294. MR 0262206 (41:6816)
  • 4. I. Blake, G. Seroussi, N. Smart, Elliptic Curves in Cryptography, London Math. Society Lecture Note Series 265, Cambridge University Press, Cambridge, 1999. MR 1771549 (2001i:94048)
  • 5. R. Bröker, A $ p$-adic algorithm to compute the Hilbert class polynomial, Math. Comp. 77 (2008), 2417-2435. MR 2429891
  • 6. H. Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics 138, Springer, New York, 1993. MR 1228206 (94i:11105)
  • 7. D. A. Cox, Primes of the form $ x\sp 2 + ny\sp 2$, John Wiley & Sons, New York, 1989. MR 1028322 (90m:11016)
  • 8. A. Enge, The complexity of class polynomial computation via floating point approximations, Math. Comp. 78 (2009), 1089-1107.
  • 9. A. Enge, Computing modular polynomials in quasi-linear time, Math. Comp. 78 (2009), 1809-1824.
  • 10. A. Enge, F. Morain, Comparing invariants for class fields of imaginary quadratric fields, in Algorithmic Number Theory (Sydney, 2002), Lect. Notes in Comput. Sci. 2369, Springer, Berlin, 2002, 252-266. MR 2041089 (2005a:11179)
  • 11. S. Galbraith, Pairings, Chapter IX of Advances in Elliptic Curve Cryptography, I. F. Blake, G. Seroussi, N. P. Smart, eds., London Math. Society Lecture Note Series 317, Cambridge University Press, Cambridge, 2005, 183-213. MR 2169215
  • 12. A. Gee, Class invariants by Shimura's reciprocity law, in Les XXèmes Journées Arithmétiques (Limoges, 1997), J. Théor. Nombres Bordeaux 11 (1999), 45-72. MR 1730432 (2000i:11171)
  • 13. A. Gee, P. Stevenhagen, Generating class fields using Shimura reciprocity, in Algorithmic Number Theory (Portland, OR, 1998), Lect. Notes in Comput. Sci. 1423, Springer, Berlin, 1998, 441-453. MR 1726092 (2000m:11112)
  • 14. B. H. Gross, Arithmetic on elliptic curves with complex multiplication, Lect. Notes in Math. 776, Springer, Berlin, 1980. MR 563921 (81f:10041)
  • 15. B. H. Gross, Minimal models for elliptic curves with complex multiplication, Compositio Math. 45 (1982), 155-164. MR 651979 (84j:14044)
  • 16. B. H. Gross, D. B. Zagier, On singular moduli, J. Reine Angew. Math. 355 (1985), 191-220. MR 772491 (86j:11041)
  • 17. IEEE 1363-2000: Standard Specifications For Public Key Cryptography, Annex A. Number-Theoretic Background, http://grouper.ieee. org/groups/1363/ private/P1363-A-11-12-99.pdf
  • 18. K. Ireland, M. Rosen, A classical introduction to modern number theory, Second Edition, Grad. Texts in Math. 84, Springer, New York, 1990. MR 1070716 (92e:11001)
  • 19. N. Ishii, Trace of Frobenius endomorphism of an elliptic curve with complex multiplication, Bull. Austral. Math. Soc. 70 (2004), 125-142. MR 2079366 (2005f:11111)
  • 20. F. Morain, Primality proving using elliptic curves: An update, in Algorithmic Number Theory (Portland, OR, 1998), Lect. Notes in Comput. Sci. 1423, Springer, Berlin, 1998, 111-127. MR 1726064 (2000i:11190)
  • 21. F. Morain, Computing the cardinality of CM elliptic curves using torsion points, J. Théor. Nombres Bordeaux 19 (2007), 663-681. MR 2388793 (2009d:11094)
  • 22. Y. Nogami, Y. Morikawa, A Method for Distinguishing the Two Candidate Elliptic Curves in CM Method, in Information Security and Cryptology -- ICISC 2004, Lect. Notes in Comput. Sci. 3506, Springer, Berlin, 2005, 249-260. MR 2214103 (2006k:94109)
  • 23. Y. Nogami, M. Obara, Y. Morikawa, A Method for Distinguishing the Two Candidate Elliptic Curves in the Complex Multiplication Method, ETRI Journal 28 (2006) 745-760.
  • 24. PARI/GP, version 2.4.0 (alpha), Bordeaux (2005), http://pari.math.u-bordeaux.fr
  • 25. A. R. Rajwade, J. C. Parnami, A new cubic character sum, Acta Arith. 40 (1981/82), 347-356. MR 667045 (83m:10065)
  • 26. K. Rubin, A. Silverberg, Point counting on reductions of CM elliptic curves, to appear in J. Number Theory (2009).
  • 27. K. Rubin, A. Silverberg, http://math.uci.edu/$ \sim$asilverb/bibliography/CMmethod.html
  • 28. R. S. Rumely, A formula for the grössencharacter of a parametrized elliptic curve, J. Number Theory 17 (1983), 389-402. MR 724537 (85e:14064)
  • 29. R. Schertz, Die singulären Werte der Weberschen Funktionen $ \mathfrak{f},\mathfrak{f}\sb{1}, \mathfrak{f}\sb{2},$ $ \gamma \sb{2},$ $ \gamma \sb{3}$, J. Reine Angew. Math. 286/287 (1976), 46-74. MR 0422213 (54:10205)
  • 30. R. Schertz, Weber's class invariants revisited, J. Théor. Nombres Bordeaux 14 (2002), 325-343. MR 1926005 (2003j:11139)
  • 31. M. Scott, A C++ Implementation of the Complex Multiplication (CM) Elliptic Curve Generation Algorithm from Annex A, in Implementations of portions of the IEEE P1363 draft, http://grouper.ieee.org/groups/1363/P1363/implementations.html
  • 32. G. Shimura, Introduction to the arithmetic theory of automorphic functions, Reprint of the 1971 original, Publications of the Mathematical Society of Japan 11, Princeton University Press, Princeton, NJ, 1994. MR 1291394 (95e:11048)
  • 33. J. Silverman, Advanced topics in the arithmetic of elliptic curves, Graduate Texts in Mathematics 151, Springer, New York, 1994. MR 1312368 (96b:11074)
  • 34. H. M. Stark, Counting points on CM elliptic curves, Rocky Mountain J. Math. 26 (1996), 1115-1138. MR 1428490 (98b:11060)
  • 35. H. Weber, Lehrbuch der Algebra, Braunschweig, 1908 (reprinted by Chelsea Publ. Co., New York, Third Reprinted Edition, 1979).

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2000): 11Y40, 11G20, 11T71, 11G15

Retrieve articles in all journals with MSC (2000): 11Y40, 11G20, 11T71, 11G15


Additional Information

K. Rubin
Affiliation: Mathematics Department, University of California, Irvine, California 92697-3875
Email: krubin@math.uci.edu

A. Silverberg
Affiliation: Mathematics Department, University of California, Irvine, California 92697-3875
Email: asilverb@math.uci.edu

DOI: https://doi.org/10.1090/S0025-5718-09-02266-2
Keywords: Elliptic curves, CM method, point-counting
Received by editor(s): June 26, 2007
Received by editor(s) in revised form: August 3, 2007, and January 20, 2009
Published electronically: July 13, 2009
Additional Notes: This material is based upon work supported by the National Science Foundation under grants DMS-0457481 and DMS-0757807 and the National Security Agency under grants H98230-05-1-0044 and H98230-07-1-0039.
Article copyright: © Copyright 2009 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society