{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T22:47:35Z","timestamp":1776725255438,"version":"3.51.2"},"reference-count":14,"publisher":"American Mathematical Society (AMS)","issue":"234","license":[{"start":{"date-parts":[[2001,3,2]],"date-time":"2001-03-02T00:00:00Z","timestamp":983491200000},"content-version":"am","delay-in-days":365,"URL":"https:\/\/www.ams.org\/publications\/copyright-and-permissions"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    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 \u201cMatch and Sort\u201d method due to Atkin. This method is a \u201cbaby step\/giant step\u201d way to find the number of points among\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper C\">\n                        <mml:semantics>\n                          <mml:mi>C<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">C<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    candidates with\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper O left-parenthesis StartRoot upper C EndRoot right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:msqrt>\n                              <mml:mi>C<\/mml:mi>\n                            <\/mml:msqrt>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">O(\\sqrt {C})<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    elliptic curve additions. Observing that the partial information modulo Atkin\u2019s 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\u2019s method requires. In practice, our technique amounts to an acceleration of Atkin\u2019s method, allowing us to count the number of points of an elliptic curve defined over\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"double-struck upper F Subscript 2 Sub Superscript 1663\">\n                        <mml:semantics>\n                          <mml:msub>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mi mathvariant=\"double-struck\">F<\/mml:mi>\n                            <\/mml:mrow>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:msup>\n                                <mml:mn>2<\/mml:mn>\n                                <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                  <mml:mn>1663<\/mml:mn>\n                                <\/mml:mrow>\n                              <\/mml:msup>\n                            <\/mml:mrow>\n                          <\/mml:msub>\n                          <mml:annotation encoding=\"application\/x-tex\">\\mathbb {F}_{2^{1663}}<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . As far as we know, this is the largest point-counting computation to date. Furthermore, the algorithm is easily parallelized.\n                  <\/p>","DOI":"10.1090\/s0025-5718-00-01200-x","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T18:17:46Z","timestamp":1027707466000},"page":"827-836","source":"Crossref","is-referenced-by-count":9,"title":["\u201cChinese &amp; Match\u201d, an alternative to Atkin\u2019s \u201cMatch and Sort\u201d method used in the SEA algorithm"],"prefix":"10.1090","volume":"70","author":[{"given":"Antoine","family":"Joux","sequence":"first","affiliation":[]},{"given":"Reynald","family":"Lercier","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2000,3,2]]},"reference":[{"key":"1","unstructured":"[Atk88] A. O. L. Atkin. The number of points on an elliptic curve modulo a prime, 1988. Email on the Number Theory Mailing List."},{"key":"2","unstructured":"[Atk91] A. O. L. Atkin. The number of points on an elliptic curve modulo a prime, 1991. Email on the Number Theory Mailing List."},{"key":"3","unstructured":"[CDM96] 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."},{"key":"4","isbn-type":"print","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/3-540-58691-1_42","article-title":"Schoof\u2019s algorithm and isogeny cycles","author":"Couveignes, Jean-Marc","year":"1994","ISBN":"https:\/\/id.crossref.org\/isbn\/3540586911"},{"key":"5","unstructured":"[Cou94] J. M. Couveignes. Quelques calculs en th\u00e9orie des nombres. th\u00e8se, Universit\u00e9 de Bordeaux I, July 1994."},{"key":"6","doi-asserted-by":"crossref","unstructured":"[Elk91] N. D. Elkies. Explicit isogenies. Draft, 1991.","DOI":"10.1155\/S1073792891000144"},{"key":"7","isbn-type":"print","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1090\/amsip\/007\/03","article-title":"Elliptic and modular curves over finite fields and related computational issues","author":"Elkies, Noam D.","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/082180880X"},{"key":"8","unstructured":"[JL98] A. Joux and R. Lercier. Cardinality of an elliptic curve defined over GF(2\u00b9\u2076\u2076\u00b3), 1998. Email on the Number Theory Mailing List."},{"key":"9","unstructured":"[Ler97] R. Lercier. Algorithmique des courbes elliptiques dans les corps finis. th\u00e8se, \u00c9cole polytechnique, June 1997."},{"key":"10","isbn-type":"print","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1090\/amsip\/007\/04","article-title":"Algorithms for computing isogenies between elliptic curves","author":"Lercier, R.","year":"1998","ISBN":"https:\/\/id.crossref.org\/isbn\/082180880X"},{"issue":"1","key":"11","doi-asserted-by":"publisher","first-page":"255","DOI":"10.5802\/jtnb.143","article-title":"Calcul du nombre de points sur une courbe elliptique dans un corps fini: aspects algorithmiques","volume":"7","author":"Morain, Fran\u00e7ois","year":"1995","journal-title":"J. Th\\'{e}or. Nombres Bordeaux","ISSN":"https:\/\/id.crossref.org\/issn\/1246-7405","issn-type":"print"},{"key":"12","unstructured":"[M{\\\"u}l95] V. M\u00fcller. Ein Algorithmus zur bestimmung der Punktanzahl elliptisher kurven \u00fcber endlichen k\u00f6rpen der charakteristik gr\u00f6\u00dfer drei. PhD thesis, Technischen Fakult\u00e4t der Universit\u00e4t des Saarlandes, February 1995."},{"issue":"170","key":"13","doi-asserted-by":"publisher","first-page":"483","DOI":"10.2307\/2007968","article-title":"Elliptic curves over finite fields and the computation of square roots mod \ud835\udc5d","volume":"44","author":"Schoof, Ren\u00e9","year":"1985","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"1","key":"14","doi-asserted-by":"publisher","first-page":"219","DOI":"10.5802\/jtnb.142","article-title":"Counting points on elliptic curves over finite fields","volume":"7","author":"Schoof, Ren\u00e9","year":"1995","journal-title":"J. Th\\'{e}or. Nombres Bordeaux","ISSN":"https:\/\/id.crossref.org\/issn\/1246-7405","issn-type":"print"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2001-70-234\/S0025-5718-00-01200-X\/S0025-5718-00-01200-X.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2001-70-234\/S0025-5718-00-01200-X\/S0025-5718-00-01200-X.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T22:35:36Z","timestamp":1776724536000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2001-70-234\/S0025-5718-00-01200-X\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,3,2]]},"references-count":14,"journal-issue":{"issue":"234","published-print":{"date-parts":[[2001,4]]}},"alternative-id":["S0025-5718-00-01200-X"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-00-01200-x","archive":["CLOCKSS","Portico"],"relation":{},"ISSN":["1088-6842","0025-5718"],"issn-type":[{"value":"1088-6842","type":"electronic"},{"value":"0025-5718","type":"print"}],"subject":[],"published":{"date-parts":[[2000,3,2]]}}}