Available in electronic format
Available in print format		 Mathematics of Computation
Journal of the American Mathematical Society
ISSN 1088-6842(e) ISSN 0025-5718(p)
Previous issue | Table of contents | Next issue
Articles in press | Recently posted articles | Most recent issue | All issues
Previous Article | Next Article
     

Choosing the correct elliptic curve in the CM method

Author(s): K. Rubin; A. Silverberg.
Journal: Math. Comp. 79 (2010), 545-561.
MSC (2000): Primary 11Y40, 11G20, 11T71, 11G15
Posted: July 13, 2009
Retrieve article in: PDF

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:

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: 10.1090/S0025-5718-09-02266-2
PII: S 0025-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
Posted: 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.
Copyright of article: Copyright 2009, American Mathematical Society
The copyright for this article reverts to public domain after 28 years from publication.

  AMS Website Logo Small Comments: webmaster@ams.org
© Copyright 2009, American Mathematical Society
Privacy Statement 		Search the AMSPowered by Google