×

zbMATH — the first resource for mathematics

“Chinese & Match”, an alternative to Atkin’s “Match and Sort” method used in the SEA algorithm. (English) Zbl 1011.11080
Summary: A classical way to compute the number of points of elliptic curves defined over finite fields from partial data obtained in SEA (Schoof-Elkies-Atkin) algorithm is a so-called “Match and Sort” method due to Atkin. This method is a “baby step/giant step” way to find the number of points among \(C\) candidates with \(O(\sqrt{C})\) elliptic curve additions. Observing that the partial information modulo Atkin’s primes is redundant, we propose to take advantage of this redundancy to eliminate the usual elliptic curve algebra in this phase of the SEA computation. This yields an algorithm of similar complexity, but the space needed is smaller than what Atkin’s method requires. In practice, our technique amounts to an acceleration of Atkin’s method, allowing us to count the number of points of an elliptic curve defined over \(\mathbb{F} _{2^{1663}}\). As far as we know, this is the largest point-counting computation to date. Furthermore, the algorithm is easily parallelized.

MSC:
11Y16 Number-theoretic algorithms; complexity
68W30 Symbolic computation and algebraic computation
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] A. O. L. Atkin. The number of points on an elliptic curve modulo a prime, 1988. Email on the Number Theory Mailing List.
[2] A. O. L. Atkin. The number of points on an elliptic curve modulo a prime, 1991. Email on the Number Theory Mailing List.
[3] 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.
[4] Jean-Marc Couveignes and François Morain, Schoof’s algorithm and isogeny cycles, Algorithmic number theory (Ithaca, NY, 1994) Lecture Notes in Comput. Sci., vol. 877, Springer, Berlin, 1994, pp. 43 – 58. · Zbl 0849.14024 · doi:10.1007/3-540-58691-1_42 · doi.org
[5] J. M. Couveignes. Quelques calculs en théorie des nombres. thèse, Université de Bordeaux I, July 1994.
[6] N. D. Elkies. Explicit isogenies. Draft, 1991.
[7] Noam D. Elkies, Elliptic and modular curves over finite fields and related computational issues, Computational perspectives on number theory (Chicago, IL, 1995) AMS/IP Stud. Adv. Math., vol. 7, Amer. Math. Soc., Providence, RI, 1998, pp. 21 – 76. · Zbl 0915.11036
[8] A. Joux and R. Lercier. Cardinality of an elliptic curve defined over GF(\(2^{1663}\)), 1998. Email on the Number Theory Mailing List.
[9] R. Lercier. Algorithmique des courbes elliptiques dans les corps finis. thèse, École polytechnique, June 1997.
[10] R. Lercier and F. Morain, Algorithms for computing isogenies between elliptic curves, Computational perspectives on number theory (Chicago, IL, 1995) AMS/IP Stud. Adv. Math., vol. 7, Amer. Math. Soc., Providence, RI, 1998, pp. 77 – 96. · Zbl 0922.11110
[11] François Morain, Calcul du nombre de points sur une courbe elliptique dans un corps fini: aspects algorithmiques, J. Théor. Nombres Bordeaux 7 (1995), no. 1, 255 – 282 (French, with English and French summaries). Les Dix-huitièmes Journées Arithmétiques (Bordeaux, 1993). · Zbl 0843.11030
[12] V. Müller. Ein Algorithmus zur bestimmung der Punktanzahl elliptisher kurven über endlichen körpen der charakteristik größer drei. PhD thesis, Technischen Fakultät der Universität des Saarlandes, February 1995.
[13] René Schoof, Elliptic curves over finite fields and the computation of square roots mod \?, Math. Comp. 44 (1985), no. 170, 483 – 494. · Zbl 0579.14025
[14] René Schoof, Counting points on elliptic curves over finite fields, J. Théor. Nombres Bordeaux 7 (1995), no. 1, 219 – 254. Les Dix-huitièmes Journées Arithmétiques (Bordeaux, 1993). · Zbl 0852.11073
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.