Computing the cardinality of CM elliptic curves using torsion points

François Morain[1]

  • [1] Laboratoire d’Informatique de l’École polytechnique (LIX) F-91128 Palaiseau Cedex France

Journal de Théorie des Nombres de Bordeaux (2007)

  • Volume: 19, Issue: 3, page 663-681
  • ISSN: 1246-7405

Abstract

top
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.

How to cite

top

Morain, François. "Computing the cardinality of CM elliptic curves using torsion points." Journal de Théorie des Nombres de Bordeaux 19.3 (2007): 663-681. <http://eudml.org/doc/249967>.

@article{Morain2007,
abstract = {Let $\mathcal\{E\}/\overline\{\mathbb\{Q\}\}$ be an elliptic curve having complex multiplication by a given quadratic order of an imaginary quadratic field $\mathbb\{K\}$. The field of definition of $\mathcal\{E\}$ is the ring class field $\Omega $ of the order. If the prime $p$ splits completely in $\Omega $, then we can reduce $\mathcal\{E\}$ modulo one the factors of $p$ and get a curve $E$ defined over $\mathbb\{F\}_\{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.},
affiliation = {Laboratoire d’Informatique de l’École polytechnique (LIX) F-91128 Palaiseau Cedex France},
author = {Morain, François},
journal = {Journal de Théorie des Nombres de Bordeaux},
keywords = {Elliptic curves; complex multiplication; modular curves; class invariants; ECPP algorithm; SEA algorithm; elliptic curves},
language = {eng},
number = {3},
pages = {663-681},
publisher = {Université Bordeaux 1},
title = {Computing the cardinality of CM elliptic curves using torsion points},
url = {http://eudml.org/doc/249967},
volume = {19},
year = {2007},
}

TY - JOUR
AU - Morain, François
TI - Computing the cardinality of CM elliptic curves using torsion points
JO - Journal de Théorie des Nombres de Bordeaux
PY - 2007
PB - Université Bordeaux 1
VL - 19
IS - 3
SP - 663
EP - 681
AB - Let $\mathcal{E}/\overline{\mathbb{Q}}$ be an elliptic curve having complex multiplication by a given quadratic order of an imaginary quadratic field $\mathbb{K}$. The field of definition of $\mathcal{E}$ is the ring class field $\Omega $ of the order. If the prime $p$ splits completely in $\Omega $, then we can reduce $\mathcal{E}$ modulo one the factors of $p$ and get a curve $E$ defined over $\mathbb{F}_{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.
LA - eng
KW - Elliptic curves; complex multiplication; modular curves; class invariants; ECPP algorithm; SEA algorithm; elliptic curves
UR - http://eudml.org/doc/249967
ER -

References

top
  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. Zbl0792.11056MR1199989
  4. B. J. Birch, Weber’s class invariants. Mathematika 16 (1969), 283–294. Zbl0226.12005
  5. C. Cailler, Sur les congruences du troisième degré. Enseign. Math. 10 (1902), 474–487. Zbl39.0257.01
  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. Zbl0849.14024
  8. D. A. Cox, Primes of the form x 2 + n y 2 . John Wiley & Sons, 1989. Zbl0701.11001MR1028322
  9. L. Dewaghe, Remarks on the Schoof-Elkies-Atkin algorithm. Math. Comp. 67(223) (July 1998), 1247–1252. Zbl0892.11038MR1468941
  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. Zbl0915.11036MR1486831
  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. Zbl1058.11077MR2041089
  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. Zbl1116.14027MR2079366
  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. Zbl0841.11042MR1361563
  14. E. Lehmer, On some special quartic reciprocity law. Acta Arith. XXI (1972), 367–377. Zbl0215.06503MR302603
  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. Zbl0874.11044MR1453209
  16. M. Maurer and V. Müller, Finding the eigenvalue in Elkies’ algorithm. Experiment. Math. 10(2) (2001), 275–285. Zbl1065.11044
  17. F. Morain, Courbes elliptiques et tests de primalité. Thèse, Université Claude Bernard–Lyon I, September 1990. MR1288092
  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. Zbl0843.11030MR1413579
  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. Zbl0908.11061MR1726064
  20. F. Morain, Implementing the asymptotically fast version of the elliptic curve primality proving algorithm. Math. Comp. 76 (2007), 493–505. Zbl1127.11084MR2261033
  21. M. Newman, Construction and application of a class of modular functions. Proc. London Math. Soc. (3) 7 (1957), 334–350. Zbl0097.28701MR91352
  22. M. Newman, Construction and application of a class of modular functions (II). Proc. London Math. Soc. (3) 9 (1959), 373–387. Zbl0178.43001MR107629
  23. R. Padma and S. Venkataraman, Elliptic curves with complex multiplication and a character sum. J. Number Theory 61 (1996), 274–282. Zbl0872.11035MR1423053
  24. R. Schertz, Weber’s class invariants revisited. J. Théor. Nombres Bordeaux 14 (2002), 325–343. Zbl1022.11056
  25. R. Schoof, Counting points on elliptic curves over finite fields. J. Théor. Nombres Bordeaux 7 (1995), 219–254. Zbl0852.11073MR1413578
  26. J. H. Silverman, The arithmetic of elliptic curves, volume 106 of Grad. Texts in Math. Springer, 1986. Zbl0585.14026MR817210
  27. J. H. SilvermanAdvanced Topics in the Arithmetic of Elliptic Curves, volume 151 of Grad. Texts in Math. Springer-Verlag, 1994. Zbl0911.14015MR1312368
  28. Th. Skolem, The general congruence of 4th degree modulo p , p prime. Norsk. Mat. Tidsskr 34 (1952), 73–80. Zbl0048.02905MR50603
  29. H. M. Stark, Counting points on CM elliptic curves. Rocky Mountain J. Math. 26(3) (1996), 1115–1138. Zbl0883.11026MR1428490
  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. Zbl0225.14014MR294345
  31. H. Weber, Lehrbuch der Algebra, volume I, II, III. Chelsea Publishing Company, New York, 1902. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.