Choosing the correct elliptic curve in the CM method

Rubin, K.; Silverberg, A.

doi:10.1090/S0025-5718-09-02266-2

Choosing the correct elliptic curve in the CM method
HTML articles powered by AMS MathViewer

by K. Rubin and A. Silverberg PDF

Math. Comp. 79 (2010), 545-561 Request permission

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

A. O. L. Atkin and F. Morain, Elliptic curves and primality proving, Math. Comp. 61 (1993), no. 203, 29–68. MR 1199989, DOI 10.1090/S0025-5718-1993-1199989-X
Juliana Belding, Reinier Bröker, Andreas Enge, and Kristin Lauter, Computing Hilbert class polynomials, Algorithmic number theory, Lecture Notes in Comput. Sci., vol. 5011, Springer, Berlin, 2008, pp. 282–295. MR 2467854, DOI 10.1007/978-3-540-79456-1_{1}9
B. J. Birch, Weber’s class invariants, Mathematika 16 (1969), 283–294. MR 262206, DOI 10.1112/S0025579300008251
I. F. Blake, G. Seroussi, and N. P. Smart, Elliptic curves in cryptography, London Mathematical Society Lecture Note Series, vol. 265, Cambridge University Press, Cambridge, 2000. Reprint of the 1999 original. MR 1771549
Reinier Bröker, A $p$-adic algorithm to compute the Hilbert class polynomial, Math. Comp. 77 (2008), no. 264, 2417–2435. MR 2429891, DOI 10.1090/S0025-5718-08-02091-7
Henri Cohen, A course in computational algebraic number theory, Graduate Texts in Mathematics, vol. 138, Springer-Verlag, Berlin, 1993. MR 1228206, DOI 10.1007/978-3-662-02945-9
David A. Cox, Primes of the form $x^2 + ny^2$, A Wiley-Interscience Publication, John Wiley & Sons, Inc., New York, 1989. Fermat, class field theory and complex multiplication. MR 1028322
A. Enge, The complexity of class polynomial computation via floating point approximations, Math. Comp. 78 (2009), 1089–1107.
A. Enge, Computing modular polynomials in quasi-linear time, Math. Comp. 78 (2009), 1809–1824.
Andreas Enge and François Morain, Comparing invariants for class fields of imaginary quadratric fields, Algorithmic number theory (Sydney, 2002) Lecture Notes in Comput. Sci., vol. 2369, Springer, Berlin, 2002, pp. 252–266. MR 2041089, DOI 10.1007/3-540-45455-1_{2}1
S. Galbraith, Pairings, Advances in elliptic curve cryptography, London Math. Soc. Lecture Note Ser., vol. 317, Cambridge Univ. Press, Cambridge, 2005, pp. 183–213. MR 2169215, DOI 10.1017/CBO9780511546570.011
Alice Gee, Class invariants by Shimura’s reciprocity law, J. Théor. Nombres Bordeaux 11 (1999), no. 1, 45–72 (English, with English and French summaries). Les XXèmes Journées Arithmétiques (Limoges, 1997). MR 1730432
Alice Gee and Peter Stevenhagen, Generating class fields using Shimura reciprocity, Algorithmic number theory (Portland, OR, 1998) Lecture Notes in Comput. Sci., vol. 1423, Springer, Berlin, 1998, pp. 441–453. MR 1726092, DOI 10.1007/BFb0054883
Benedict H. Gross, Arithmetic on elliptic curves with complex multiplication, Lecture Notes in Mathematics, vol. 776, Springer, Berlin, 1980. With an appendix by B. Mazur. MR 563921
Benedict H. Gross, Minimal models for elliptic curves with complex multiplication, Compositio Math. 45 (1982), no. 2, 155–164. MR 651979
Benedict H. Gross and Don B. Zagier, On singular moduli, J. Reine Angew. Math. 355 (1985), 191–220. MR 772491
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
Kenneth Ireland and Michael Rosen, A classical introduction to modern number theory, 2nd ed., Graduate Texts in Mathematics, vol. 84, Springer-Verlag, New York, 1990. MR 1070716, DOI 10.1007/978-1-4757-2103-4
Noburo Ishii, Trace of Frobenius endomorphism of an elliptic curve with complex multiplication, Bull. Austral. Math. Soc. 70 (2004), no. 1, 125–142. MR 2079366, DOI 10.1017/S0004972700035875
F. Morain, Primality proving using elliptic curves: an update, Algorithmic number theory (Portland, OR, 1998) Lecture Notes in Comput. Sci., vol. 1423, Springer, Berlin, 1998, pp. 111–127. MR 1726064, DOI 10.1007/BFb0054855
François Morain, Computing the cardinality of CM elliptic curves using torsion points, J. Théor. Nombres Bordeaux 19 (2007), no. 3, 663–681 (English, with English and French summaries). MR 2388793
Yasuyuki Nogami and Yoshitaka Morikawa, A method for distinguishing the two candidate elliptic curves in CM method, Information security and cryptology—ICISC 2004, Lecture Notes in Comput. Sci., vol. 3506, Springer, Berlin, 2005, pp. 249–260. MR 2214103, DOI 10.1007/11496618_{1}9
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.
PARI/GP, version 2.4.0 (alpha), Bordeaux (2005), http://pari.math.u-bordeaux.fr
A. R. Rajwade and J. C. Parnami, A new cubic character sum, Acta Arith. 40 (1981/82), no. 4, 347–356. MR 667045, DOI 10.4064/aa-40-4-347-356
K. Rubin, A. Silverberg, Point counting on reductions of CM elliptic curves, to appear in J. Number Theory (2009).
K. Rubin, A. Silverberg, http://math.uci.edu/$\sim$asilverb/bibliography/CMmethod.html
Robert S. Rumely, A formula for the grössencharacter of a parametrized elliptic curve, J. Number Theory 17 (1983), no. 3, 389–402. MR 724537, DOI 10.1016/0022-314X(83)90056-2
Reinhard Schertz, Die singulären Werte der Weberschen Funktionen $\mathfrak {f},\mathfrak {f}sb{1},\mathfrak {f}_{2},$ $\gamma _{2},$ $\gamma _{3}$, J. Reine Angew. Math. 286(287) (1976), 46–74 (German). MR 422213, DOI 10.1515/crll.1976.286-287.46
Reinhard Schertz, Weber’s class invariants revisited, J. Théor. Nombres Bordeaux 14 (2002), no. 1, 325–343 (English, with English and French summaries). MR 1926005
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
Goro Shimura, Introduction to the arithmetic theory of automorphic functions, Publications of the Mathematical Society of Japan, vol. 11, Princeton University Press, Princeton, NJ, 1994. Reprint of the 1971 original; Kanô Memorial Lectures, 1. MR 1291394
Joseph H. Silverman, Advanced topics in the arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 151, Springer-Verlag, New York, 1994. MR 1312368, DOI 10.1007/978-1-4612-0851-8
H. M. Stark, Counting points on CM elliptic curves, Rocky Mountain J. Math. 26 (1996), no. 3, 1115–1138. Symposium on Diophantine Problems (Boulder, CO, 1994). MR 1428490, DOI 10.1216/rmjm/1181072041
H. Weber, Lehrbuch der Algebra, Braunschweig, 1908 (reprinted by Chelsea Publ. Co., New York, Third Reprinted Edition, 1979).