{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T22:37:59Z","timestamp":1776724679106,"version":"3.51.2"},"reference-count":20,"publisher":"American Mathematical Society (AMS)","issue":"223","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Comp."],"abstract":"<p>\n                    Schoof\u2019s algorithm computes the number\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"m\">\n                        <mml:semantics>\n                          <mml:mi>m<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">m<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    of points on an elliptic curve\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper E\">\n                        <mml:semantics>\n                          <mml:mi>E<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">E<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    defined over a finite field\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 q\">\n                        <mml:semantics>\n                          <mml:msub>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                <mml:mi mathvariant=\"double-struck\">F<\/mml:mi>\n                              <\/mml:mrow>\n                            <\/mml:mrow>\n                            <mml:mi>q<\/mml:mi>\n                          <\/mml:msub>\n                          <mml:annotation encoding=\"application\/x-tex\">{\\Bbb F}_q<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . Schoof determines\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"m\">\n                        <mml:semantics>\n                          <mml:mi>m<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">m<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    modulo small primes\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"script l\">\n                        <mml:semantics>\n                          <mml:mi>\n                            \u2113\n                            \n                          <\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">\\ell<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    using the characteristic equation of the Frobenius of\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper E\">\n                        <mml:semantics>\n                          <mml:mi>E<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">E<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    and polynomials of degree\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper O left-parenthesis script l squared right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:msup>\n                              <mml:mi>\n                                \u2113\n                                \n                              <\/mml:mi>\n                              <mml:mn>2<\/mml:mn>\n                            <\/mml:msup>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">O(\\ell ^2)<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . With the works of Elkies and Atkin, we have just to compute, when\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"script l\">\n                        <mml:semantics>\n                          <mml:mi>\n                            \u2113\n                            \n                          <\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">\\ell<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    is a \u201cgood\" prime, an eigenvalue of the Frobenius using polynomials of degree\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper O left-parenthesis script l right-parenthesis\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>O<\/mml:mi>\n                            <mml:mo stretchy=\"false\">(<\/mml:mo>\n                            <mml:mi>\n                              \u2113\n                              \n                            <\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">O(\\ell )<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    . In this article, we compute the complexity of M\u00fcller\u2019s algorithm, which is the best known method for determining one eigenvalue and we improve the final step in some cases. Finally, when\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"script l\">\n                        <mml:semantics>\n                          <mml:mi>\n                            \u2113\n                            \n                          <\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">\\ell<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    is \u201cbad\", we describe how to have polynomials of small degree and how to perform computations, in Schoof\u2019s algorithm, on\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"x\">\n                        <mml:semantics>\n                          <mml:mi>x<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">x<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    -values only.\n                  <\/p>","DOI":"10.1090\/s0025-5718-98-00962-4","type":"journal-article","created":{"date-parts":[[2002,7,26]],"date-time":"2002-07-26T18:14:44Z","timestamp":1027707284000},"page":"1247-1252","source":"Crossref","is-referenced-by-count":15,"title":["Remarks on the Schoof-Elkies-Atkin algorithm"],"prefix":"10.1090","volume":"67","author":[{"given":"L.","family":"Dewaghe","sequence":"first","affiliation":[]}],"member":"14","published-online":{"date-parts":[[1998]]},"reference":[{"key":"1","unstructured":"A. O. L. Atkin, The number of points on an elliptic curve modulo a prime (I).  Draft, 1988."},{"key":"2","unstructured":"A. O. L. Atkin, The number of points on an elliptic curve modulo a prime (II).  Draft, 1992."},{"key":"3","doi-asserted-by":"publisher","first-page":"425","DOI":"10.2307\/2303037","article-title":"Series for all the roots of the equation (\ud835\udc67-\ud835\udc4e)^{\ud835\udc5a}=\ud835\udc58(\ud835\udc67-\ud835\udc4f)\u207f","volume":"46","author":"Eagle, Albert","year":"1939","journal-title":"Amer. Math. Monthly","ISSN":"https:\/\/id.crossref.org\/issn\/0002-9890","issn-type":"print"},{"issue":"4","key":"4","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1145\/322092.322099","article-title":"Fast algorithms for manipulating formal power series","volume":"25","author":"Brent, R. P.","year":"1978","journal-title":"J. Assoc. Comput. Mach.","ISSN":"https:\/\/id.crossref.org\/issn\/0004-5411","issn-type":"print"},{"key":"5","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":"6","unstructured":"J.-M. Couveignes, L. Dewaghe, F. Morain, Isogeny cycles and Schoof\u2019s algorithm, Preprint 1995."},{"key":"7","unstructured":"J.-M. Couveignes, Quelques calculs en th\u00e9orie des nombres, Th\u00e8se, Universit\u00e9 de Bordeaux I, July 1994."},{"key":"8","unstructured":"L. Dewaghe, Nombre de points d\u2019une courbe elliptique sur un corps fini, Th\u00e8se, Universit\u00e9 de Lille I, 1996."},{"key":"9","series-title":"The Kluwer International Series in Engineering and Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-1983-2","volume-title":"Finite fields for computer scientists and engineers","volume":"23","author":"McEliece, Robert J.","year":"1987","ISBN":"https:\/\/id.crossref.org\/isbn\/0898381916"},{"key":"10","doi-asserted-by":"crossref","unstructured":"N. D. Elkies, Explicit Isogenies, Draft, 1991.","DOI":"10.1155\/S1073792891000144"},{"key":"11","series-title":"Addison-Wesley Series in Computer Science and Information Processing","isbn-type":"print","volume-title":"The art of computer programming. Vol. 2","author":"Knuth, Donald E.","year":"1981","ISBN":"https:\/\/id.crossref.org\/isbn\/0201038226","edition":"2"},{"key":"12","isbn-type":"print","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1007\/3-540-49264-X_7","article-title":"Counting the number of points on elliptic curves over finite fields: strategies and performances","author":"Lercier, Reynald","year":"1995","ISBN":"https:\/\/id.crossref.org\/isbn\/3540594094"},{"key":"13","unstructured":"R. Lercier, F. Morain, Counting points on elliptic curves over \ud835\udd3d_{\ud835\udd61\u207f} using Couveignes\u2019s algorithm. Research Report LIX\/RR\/95\/09, Ecole polytechnique - LIX, September 1995."},{"issue":"201","key":"14","doi-asserted-by":"publisher","first-page":"407","DOI":"10.2307\/2153177","article-title":"Counting points on elliptic curves over \ud835\udc05_{2^{\ud835\udc26}}","volume":"60","author":"Menezes, Alfred J.","year":"1993","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"1","key":"15","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":"16","unstructured":"V. M\u00fcller, Looking for the eigenvalue in Schoof\u2019s algorithm, In preparation, October 1994."},{"issue":"170","key":"17","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":"18","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"},{"issue":"4","key":"19","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1006\/jsco.1995.1055","article-title":"A new polynomial factorization algorithm and its implementation","volume":"20","author":"Shoup, Victor","year":"1995","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"key":"20","series-title":"Graduate Texts in Mathematics","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-1920-8","volume-title":"The arithmetic of elliptic curves","volume":"106","author":"Silverman, Joseph H.","year":"1986","ISBN":"https:\/\/id.crossref.org\/isbn\/0387962034"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/1998-67-223\/S0025-5718-98-00962-4\/S0025-5718-98-00962-4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/1998-67-223\/S0025-5718-98-00962-4\/S0025-5718-98-00962-4.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,20]],"date-time":"2026-04-20T21:48:48Z","timestamp":1776721728000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/1998-67-223\/S0025-5718-98-00962-4\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"references-count":20,"journal-issue":{"issue":"223","published-print":{"date-parts":[[1998,7]]}},"alternative-id":["S0025-5718-98-00962-4"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-98-00962-4","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":[[1998]]}}}