Computing the cardinality of CM elliptic curves using torsion points

Morain, François

Journal de théorie des nombres de Bordeaux, Tome 19 (2007) no. 3, pp. 663-681.

Soit $ℰ/\overline{\mathbb{Q}}$ une courbe elliptique avec multiplications complexes par un ordre d’un corps quadratique imaginaire $𝕂$. Le corps de définition de $ℰ$ est le corps de classe de rayon $\Omega$ associé à l’ordre. Si le nombre premier $p$ est scindé dans $\Omega$, on peut réduire $ℰ$ modulo un des facteurs de $p$ et obtenir une courbe $E$ définie sur ${𝔽}_p$. La trace du Frobenius de $E$ est connue au signe près et nous cherchons à déterminer ce signe de la manière la plus rapide possible, avec comme application l’algorithme de primalité ECPP. Dans ce but, nous expliquons comment utiliser l’action du Frobenius sur des points de torsion d’ordre petit obtenus à partir d’invariants de classes qui généralisent les fonctions de Weber.

Let $ℰ/\overline{\mathbb{Q}}$ be an elliptic curve having complex multiplication by a given quadratic order of an imaginary quadratic field $𝕂$. The field of definition of $ℰ$ is the ring class field $\Omega$ of the order. If the prime $p$ splits completely in $\Omega$, then we can reduce $ℰ$ modulo one the factors of $p$ and get a curve $E$ defined over ${𝔽}_p$. The trace of the Frobenius of $E$ is known up to sign and we need a fast way to find this sign, in the context of the Elliptic Curve Primality Proving algorithm (ECPP). For this purpose, we propose to use the action of the Frobenius on torsion points of small order built with class invariants generalizing the classical Weber functions.

Mots clés : Elliptic curves, complex multiplication, modular curves, class invariants, ECPP algorithm, SEA algorithm.

[1] A. O. L. Atkin, The number of points on an elliptic curve modulo a prime (II). Draft. Available on http://listserv.nodak.edu/archives/nmbrthry.html, 1992.

[2] A. O. L. Atkin, Probabilistic primality testing, In P. Flajolet and P. Zimmermann, editors, Analysis of Algorithms Seminar I. INRIA Research Report XXX, 1992. Summary by F. Morain. Available as http://pauillac.inria.fr/algo/seminars/sem91-92/atkin.ps.

[3] A. O. L. Atkin and F. Morain, Elliptic curves and primality proving. Math. Comp. 61(203) (July 1993), 29–68. | MR | Zbl

[4] B. J. Birch, Weber’s class invariants. Mathematika 16 (1969), 283–294. | Zbl

[5] C. Cailler, Sur les congruences du troisième degré. Enseign. Math. 10 (1902), 474–487.

[6] J.-M. Couveignes, L. Dewaghe, and F. Morain, Isogeny cycles and the Schoof-Elkies-Atkin algorithm. Research Report LIX/RR/96/03, LIX, April 1996.

[7] J.-M. Couveignes and F. Morain, Schoof’s algorithm and isogeny cycles. In L. Adleman and M.-D. Huang, editors, Algorithmic Number Theory, volume 877 of Lecture Notes in Comput. Sci., pages 43–58. Springer-Verlag, 1994. 1st Algorithmic Number Theory Symposium - Cornell University, May 6-9, 1994. | Zbl

[8] D. A. Cox, Primes of the form $x^2+n{y}^2$. John Wiley & Sons, 1989. | MR | Zbl

[9] L. Dewaghe, Remarks on the Schoof-Elkies-Atkin algorithm. Math. Comp. 67(223) (July 1998), 1247–1252. | MR | Zbl

[10] N. D. Elkies, Elliptic and modular curves over finite fields and related computational issues. In D. A. Buell and J. T. Teitelbaum, editors, Computational Perspectives on Number Theory: Proceedings of a Conference in Honor of A. O. L. Atkin, volume 7 of AMS/IP Studies in Advanced Mathematics, pages 21–76. American Mathematical Society, International Press, 1998. | MR | Zbl

[11] A. Enge and F. Morain, Comparing invariants for class fields of imaginary quadratic fields. In C. Fieker and D. R. Kohel, editors, Algorithmic Number Theory, volume 2369 of Lecture Notes in Comput. Sci., pages 252–266. Springer-Verlag, 2002. 5th International Symposium, ANTS-V, Sydney, Australia, July 2002, Proceedings. | MR | Zbl

[12] N. Ishii, Trace of Frobenius endomorphism of an elliptic curve with complex multiplication. Available at , January 2004. | arXiv | MR | Zbl

[13] A. Joux and F. Morain, Sur les sommes de caractères liées aux courbes elliptiques à multiplication complexe. J. Number Theory 55(1) (1995), 108–128. | MR | Zbl

[14] E. Lehmer, On some special quartic reciprocity law. Acta Arith. XXI (1972), 367–377. | MR | Zbl

[15] F. Leprévost and F. Morain, Revêtements de courbes elliptiques à multiplication complexe par des courbes hyperelliptiques et sommes de caractères. J. Number Theory 64 (1997), 165–182. | MR | Zbl

[16] M. Maurer and V. Müller, Finding the eigenvalue in Elkies’ algorithm. Experiment. Math. 10(2) (2001), 275–285. | Zbl

[17] F. Morain, Courbes elliptiques et tests de primalité. Thèse, Université Claude Bernard–Lyon I, September 1990. | MR

[18] F. Morain, Calcul du nombre de points sur une courbe elliptique dans un corps fini : aspects algorithmiques. J. Théor. Nombres Bordeaux 7 (1995), 255–282. | Numdam | MR | Zbl

[19] F. Morain, Primality proving using elliptic curves: an update. In J. P. Buhler, editor, Algorithmic Number Theory, volume 1423 of Lecture Notes in Comput. Sci., pages 111–127. Springer-Verlag, 1998. Third International Symposium, ANTS-III, Portland, Oregon, june 1998, Proceedings. | MR | Zbl

[20] F. Morain, Implementing the asymptotically fast version of the elliptic curve primality proving algorithm. Math. Comp. 76 (2007), 493–505. | MR | Zbl

[21] M. Newman, Construction and application of a class of modular functions. Proc. London Math. Soc. (3) 7 (1957), 334–350. | MR | Zbl

[22] M. Newman, Construction and application of a class of modular functions (II). Proc. London Math. Soc. (3) 9 (1959), 373–387. | MR | Zbl

[23] R. Padma and S. Venkataraman, Elliptic curves with complex multiplication and a character sum. J. Number Theory 61 (1996), 274–282. | MR | Zbl

[24] R. Schertz, Weber’s class invariants revisited. J. Théor. Nombres Bordeaux 14 (2002), 325–343. | Numdam | Zbl

[25] R. Schoof, Counting points on elliptic curves over finite fields. J. Théor. Nombres Bordeaux 7 (1995), 219–254. | Numdam | MR | Zbl

[26] J. H. Silverman, The arithmetic of elliptic curves, volume 106 of Grad. Texts in Math. Springer, 1986. | MR | Zbl

[27] J. H. Silverman Advanced Topics in the Arithmetic of Elliptic Curves, volume 151 of Grad. Texts in Math. Springer-Verlag, 1994. | MR | Zbl

[28] Th. Skolem, The general congruence of 4th degree modulo $p$, $p$ prime. Norsk. Mat. Tidsskr 34 (1952), 73–80. | MR | Zbl

[29] H. M. Stark, Counting points on CM elliptic curves. Rocky Mountain J. Math. 26(3) (1996), 1115–1138. | MR | Zbl

[30] J. Vélu, Isogénies entre courbes elliptiques. C. R. Acad. Sci. Paris Sér. I Math. 273 (July 1971), 238–241. Série A. | MR | Zbl

[31] H. Weber, Lehrbuch der Algebra, volume I, II, III. Chelsea Publishing Company, New York, 1902.