Computing the cardinality of CM elliptic curves using torsion points
Journal de théorie des nombres de Bordeaux, Volume 19 (2007) no. 3, p. 663-681

Let / ¯ 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 Ω of the order. If the prime p splits completely in Ω, 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.

Soit / ¯ 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 Ω associé à l’ordre. Si le nombre premier p est scindé dans Ω, 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.

DOI : https://doi.org/10.5802/jtnb.607
Keywords: Elliptic curves, complex multiplication, modular curves, class invariants, ECPP algorithm, SEA algorithm.
@article{JTNB_2007__19_3_663_0,
     author = {Morain, Fran\c cois},
     title = {Computing the cardinality of CM elliptic curves using torsion points},
     journal = {Journal de th\'eorie des nombres de Bordeaux},
     publisher = {Universit\'e Bordeaux 1},
     volume = {19},
     number = {3},
     year = {2007},
     pages = {663-681},
     doi = {10.5802/jtnb.607},
     mrnumber = {2388793},
     zbl = {1196.11085},
     language = {en},
     url = {http://www.numdam.org/item/JTNB_2007__19_3_663_0}
}
Morain, François. Computing the cardinality of CM elliptic curves using torsion points. Journal de théorie des nombres de Bordeaux, Volume 19 (2007) no. 3, pp. 663-681. doi : 10.5802/jtnb.607. http://www.numdam.org/item/JTNB_2007__19_3_663_0/

[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 1199989 | Zbl 0792.11056

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

[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 0849.14024

[8] D. A. Cox, Primes of the form x 2 +ny 2 . John Wiley & Sons, 1989. | MR 1028322 | Zbl 0701.11001

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

[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 1486831 | Zbl 0915.11036

[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 2041089 | Zbl 1058.11077

[12] N. Ishii, Trace of Frobenius endomorphism of an elliptic curve with complex multiplication. Available at http://arxiv.org/abs/math.NT/0401289, January 2004. | MR 2079366 | Zbl 1116.14027

[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 1361563 | Zbl 0841.11042

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

[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 1453209 | Zbl 0874.11044

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

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

[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 1413579 | Zbl 0843.11030

[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 1726064 | Zbl 0908.11061

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

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

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

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

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

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

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

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

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

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

[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 294345 | Zbl 0225.14014

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