{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T18:39:39Z","timestamp":1776796779545,"version":"3.51.2"},"reference-count":43,"publisher":"American Mathematical Society (AMS)","issue":"285","license":[{"start":{"date-parts":[[2014,5,3]],"date-time":"2014-05-03T00:00:00Z","timestamp":1399075200000},"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                    We propose a simple deterministic test for deciding whether or not an element\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"a element-of double-struck upper F Subscript 2 Sub Superscript n Superscript times\">\n                        <mml:semantics>\n                          <mml:mrow>\n                            <mml:mi>a<\/mml:mi>\n                            <mml:mo>\n                              \u2208\n                              \n                            <\/mml:mo>\n                            <mml:msubsup>\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:mi>n<\/mml:mi>\n                                <\/mml:msup>\n                              <\/mml:mrow>\n                              <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                                <mml:mo>\n                                  \u00d7\n                                  \n                                <\/mml:mo>\n                              <\/mml:mrow>\n                            <\/mml:msubsup>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">a \\in \\mathbb {F}_{2^n}^{\\times }<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    or\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 3 Sub Superscript n Superscript times\">\n                        <mml:semantics>\n                          <mml:msubsup>\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>3<\/mml:mn>\n                                <mml:mi>n<\/mml:mi>\n                              <\/mml:msup>\n                            <\/mml:mrow>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mo>\n                                \u00d7\n                                \n                              <\/mml:mo>\n                            <\/mml:mrow>\n                          <\/mml:msubsup>\n                          <mml:annotation encoding=\"application\/x-tex\">\\mathbb {F}_{3^n}^{\\times }<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    is a zero of the corresponding Kloosterman sum over these fields, and rigorously analyse its runtime. The test seems to have been overlooked in the literature. The expected cost of the test for binary fields is a single point-halving on an associated elliptic curve, while for ternary fields the expected cost is one-half of a point-thirding on an associated elliptic curve. For binary fields of practical interest, this represents an\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"upper O left-parenthesis n 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<\/mml:mi>\n                            <mml:mo stretchy=\"false\">)<\/mml:mo>\n                          <\/mml:mrow>\n                          <mml:annotation encoding=\"application\/x-tex\">O(n)<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    speedup over the previous fastest test. By repeatedly invoking the test on random elements of\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 n Superscript times\">\n                        <mml:semantics>\n                          <mml:msubsup>\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:mi>n<\/mml:mi>\n                              <\/mml:msup>\n                            <\/mml:mrow>\n                            <mml:mrow class=\"MJX-TeXAtom-ORD\">\n                              <mml:mo>\n                                \u00d7\n                                \n                              <\/mml:mo>\n                            <\/mml:mrow>\n                          <\/mml:msubsup>\n                          <mml:annotation encoding=\"application\/x-tex\">\\mathbb {F}_{2^n}^{\\times }<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    we obtain the most efficient probabilistic method to date to find non-trivial Kloosterman sum zeros. The analysis depends on the distribution of Sylow\n                    <inline-formula content-type=\"math\/mathml\">\n                      <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\" alttext=\"p\">\n                        <mml:semantics>\n                          <mml:mi>p<\/mml:mi>\n                          <mml:annotation encoding=\"application\/x-tex\">p<\/mml:annotation>\n                        <\/mml:semantics>\n                      <\/mml:math>\n                    <\/inline-formula>\n                    -subgroups in the two families of associated elliptic curves, which we ascertain using a theorem due to Howe.\n                  <\/p>","DOI":"10.1090\/s0025-5718-2013-02705-6","type":"journal-article","created":{"date-parts":[[2013,5,3]],"date-time":"2013-05-03T10:07:07Z","timestamp":1367575627000},"page":"347-363","source":"Crossref","is-referenced-by-count":3,"title":["An efficient deterministic test for Kloosterman sum zeros"],"prefix":"10.1090","volume":"83","author":[{"given":"Omran","family":"Ahmadi","sequence":"first","affiliation":[]},{"given":"Robert","family":"Granger","sequence":"additional","affiliation":[]}],"member":"14","published-online":{"date-parts":[[2013,5,3]]},"reference":[{"issue":"3","key":"1","doi-asserted-by":"publisher","first-page":"493","DOI":"10.1007\/s10623-004-4039-4","article-title":"On the number of trace-one elements in polynomial bases for \ud835\udd3d_{2\u207f}","volume":"37","author":"Ahmadi, Omran","year":"2005","journal-title":"Des. Codes Cryptogr.","ISSN":"https:\/\/id.crossref.org\/issn\/0925-1022","issn-type":"print"},{"key":"2","series-title":"Techniques of Physics, No. 3","isbn-type":"print","volume-title":"Walsh functions and their applications","author":"Beauchamp, K. G.","year":"1975","ISBN":"https:\/\/id.crossref.org\/isbn\/0120840502"},{"key":"3","series-title":"London Mathematical Society Lecture Note Series","isbn-type":"print","volume-title":"Elliptic curves in cryptography","volume":"265","author":"Blake, I. F.","year":"2000","ISBN":"https:\/\/id.crossref.org\/isbn\/0521653746"},{"issue":"3-4","key":"4","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1006\/jsco.1996.0125","article-title":"The Magma algebra system. I. The user language","volume":"24","author":"Bosma, Wieb","year":"1997","journal-title":"J. Symbolic Comput.","ISSN":"https:\/\/id.crossref.org\/issn\/0747-7171","issn-type":"print"},{"issue":"2","key":"5","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/s11139-012-9444-0","article-title":"The distribution of the number of points modulo an integer on elliptic curves over finite fields","volume":"30","author":"Castryck, Wouter","year":"2013","journal-title":"Ramanujan J.","ISSN":"https:\/\/id.crossref.org\/issn\/1382-4090","issn-type":"print"},{"issue":"9","key":"6","doi-asserted-by":"publisher","first-page":"4230","DOI":"10.1109\/TIT.2008.928273","article-title":"Hyperbent functions, Kloosterman sums, and Dickson polynomials","volume":"54","author":"Charpin, Pascale","year":"2008","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"2","key":"7","doi-asserted-by":"publisher","first-page":"322","DOI":"10.1016\/j.jcta.2006.06.002","article-title":"The divisibility modulo 24 of Kloosterman sums on \ud835\udc3a\ud835\udc39(2^{\ud835\udc5a}), \ud835\udc5a odd","volume":"114","author":"Charpin, Pascale","year":"2007","journal-title":"J. Combin. Theory Ser. A","ISSN":"https:\/\/id.crossref.org\/issn\/0097-3165","issn-type":"print"},{"issue":"2","key":"8","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1016\/j.ffa.2005.08.007","article-title":"Propagation characteristics of \ud835\udc65\\mapsto\ud835\udc65\u207b\u00b9 and Kloosterman sums","volume":"13","author":"Charpin, Pascale","year":"2007","journal-title":"Finite Fields Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/1071-5797","issn-type":"print"},{"issue":"4","key":"9","doi-asserted-by":"publisher","first-page":"385","DOI":"10.1016\/0196-8858(86)90023-0","article-title":"Sequences of numbers generated by addition in formal groups and new primality and factorization tests","volume":"7","author":"Chudnovsky, D. V.","year":"1986","journal-title":"Adv. in Appl. Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0196-8858","issn-type":"print"},{"key":"10","volume-title":"ELEMENTARY HADAMARD DIFFERENCE-SETS","author":"Dillon, John Francis","year":"1974"},{"key":"11","doi-asserted-by":"crossref","unstructured":"Kenny Fong, Darrel Hankerson, Julio Lopez, and Alfred Menezes. Field inversion and point halving revisited. IEEE Transactions on Computers, 53:1047\u20131059, 2003.","DOI":"10.1109\/TC.2004.43"},{"issue":"1-3","key":"12","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1007\/s10623-008-9171-0","article-title":"On binary Kloosterman sums divisible by 3","volume":"49","author":"Garaschuk, Kseniya","year":"2008","journal-title":"Des. Codes Cryptogr.","ISSN":"https:\/\/id.crossref.org\/issn\/0925-1022","issn-type":"print"},{"issue":"4","key":"13","doi-asserted-by":"publisher","first-page":"2516","DOI":"10.1109\/TIT.2011.2176914","article-title":"Binary Kloosterman sums modulo 256 and coefficients of the characteristic polynomial","volume":"58","author":"G\u00f6lo\u011flu, Faruk","year":"2012","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"key":"14","isbn-type":"print","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1007\/978-3-642-15874-2_16","article-title":"Ternary Kloosterman sums modulo 18 using Stickelberger\u2019s theorem","author":"G\u00f6lo\u011flu, Faruk","year":"2010","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642158735"},{"issue":"3","key":"15","doi-asserted-by":"publisher","first-page":"269","DOI":"10.4064\/aa148-3-4","article-title":"Binary Kloosterman sums using Stickelberger\u2019s theorem and the Gross-Koblitz formula","volume":"148","author":"G\u00f6lo\u011flu, Faruk","year":"2011","journal-title":"Acta Arith.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"},{"key":"16","unstructured":"Faruk G\u00f6loglu, Gary McGuire, and Richard Moloney. Some congruences of Kloosterman sums and their minimal polynomials. To appear in J. Number Theory."},{"issue":"5","key":"17","doi-asserted-by":"publisher","first-page":"2018","DOI":"10.1109\/TIT.2006.872854","article-title":"Monomial and quadratic bent functions over the finite fields of odd characteristic","volume":"52","author":"Helleseth, Tor","year":"2006","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"1-3","key":"18","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1023\/A:1026491513009","article-title":"On \ud835\udc4d\u2084-linear Goethals codes and Kloosterman sums","volume":"17","author":"Helleseth, Tor","year":"1999","journal-title":"Des. Codes Cryptogr.","ISSN":"https:\/\/id.crossref.org\/issn\/0925-1022","issn-type":"print"},{"key":"19","isbn-type":"print","doi-asserted-by":"publisher","first-page":"138","DOI":"10.1007\/978-3-540-77026-8_11","article-title":"New formulae for efficient elliptic curve arithmetic","author":"Hisil, Huseyin","year":"2007","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540770251"},{"issue":"2","key":"20","first-page":"229","article-title":"On the group orders of elliptic curves over finite fields","volume":"85","author":"Howe, Everett W.","year":"1993","journal-title":"Compositio Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0010-437X","issn-type":"print"},{"key":"21","doi-asserted-by":"publisher","first-page":"96","DOI":"10.2969\/jmsj\/02010096","article-title":"On the algebraic theory of elliptic modular functions","volume":"20","author":"Igusa, Jun-ichi","year":"1968","journal-title":"J. Math. Soc. Japan","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5645","issn-type":"print"},{"key":"22","series-title":"Annals of Mathematics Studies","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1515\/9781400882120","volume-title":"Gauss sums, Kloosterman sums, and monodromy groups","volume":"116","author":"Katz, Nicholas M.","year":"1988","ISBN":"https:\/\/id.crossref.org\/isbn\/0691084327"},{"issue":"11","key":"23","first-page":"723","article-title":"Sommes de Kloosterman et courbes elliptiques universelles en caract\u00e9ristiques 2 et 3","volume":"309","author":"Katz, Nicholas","year":"1989","journal-title":"C. R. Acad. Sci. Paris S\\'{e}r. I Math.","ISSN":"https:\/\/id.crossref.org\/issn\/0764-4442","issn-type":"print"},{"key":"24","isbn-type":"print","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-540-48000-6_12","article-title":"Elliptic scalar multiplication using point halving","author":"Knudsen, Erik Woodward","year":"1999","ISBN":"https:\/\/id.crossref.org\/isbn\/3540666664"},{"issue":"8","key":"25","doi-asserted-by":"publisher","first-page":"4011","DOI":"10.1109\/TIT.2010.2050806","article-title":"On integer values of Kloosterman sums","volume":"56","author":"Kononen, Keijo Petteri","year":"2010","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"3","key":"26","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1109\/18.54892","article-title":"The weights of the orthogonals of the extended quadratic binary Goppa codes","volume":"36","author":"Lachaud, Gilles","year":"1990","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"issue":"3","key":"27","doi-asserted-by":"publisher","first-page":"649","DOI":"10.2307\/1971363","article-title":"Factoring integers with elliptic curves","volume":"126","author":"Lenstra, H. W., Jr.","year":"1987","journal-title":"Ann. of Math. (2)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-486X","issn-type":"print"},{"key":"28","isbn-type":"print","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/978-3-540-85912-3_17","article-title":"On the connection between Kloosterman sums and elliptic curves","author":"Lison\u011bk, Petr","year":"2008","ISBN":"https:\/\/id.crossref.org\/isbn\/9783540859116"},{"issue":"1-3","key":"29","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/s10623-010-9457-x","article-title":"On zeros of Kloosterman sums","volume":"59","author":"Lison\u011bk, Petr","year":"2011","journal-title":"Des. Codes Cryptogr.","ISSN":"https:\/\/id.crossref.org\/issn\/0925-1022","issn-type":"print"},{"issue":"249","key":"30","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1090\/S0025-5718-04-01640-0","article-title":"Determining the 2-Sylow subgroup of an elliptic curve over a finite field","volume":"74","author":"Miret, J.","year":"2005","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"267","key":"31","doi-asserted-by":"publisher","first-page":"1767","DOI":"10.1090\/S0025-5718-08-02201-1","article-title":"Computing the \ud835\udc59-power torsion of an elliptic curve over a finite field","volume":"78","author":"Miret, J.","year":"2009","journal-title":"Math. Comp.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5718","issn-type":"print"},{"issue":"4","key":"32","doi-asserted-by":"publisher","first-page":"329","DOI":"10.4064\/aa132-4-3","article-title":"Kloosterman sums, elliptic curves, and irreducible polynomials with prescribed trace and norm","volume":"132","author":"Moisio, Marko","year":"2008","journal-title":"Acta Arith.","ISSN":"https:\/\/id.crossref.org\/issn\/0065-1036","issn-type":"print"},{"issue":"2","key":"33","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1016\/j.ffa.2008.11.001","article-title":"The divisibility modulo 24 of Kloosterman sums on \ud835\udc3a\ud835\udc39(2^{\ud835\udc5a}), \ud835\udc5a even","volume":"15","author":"Moisio, Marko","year":"2009","journal-title":"Finite Fields Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/1071-5797","issn-type":"print"},{"issue":"4","key":"34","doi-asserted-by":"publisher","first-page":"922","DOI":"10.1016\/j.ffa.2006.05.002","article-title":"Kloosterman sum identities and low-weight codewords in a cyclic code with two zeros","volume":"13","author":"Moisio, Marko","year":"2007","journal-title":"Finite Fields Appl.","ISSN":"https:\/\/id.crossref.org\/issn\/1071-5797","issn-type":"print"},{"issue":"3","key":"35","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1007\/BF01190214","article-title":"The distribution of values of Kloosterman sums","volume":"56","author":"Niederreiter, Harald","year":"1991","journal-title":"Arch. Math. (Basel)","ISSN":"https:\/\/id.crossref.org\/issn\/0003-889X","issn-type":"print"},{"issue":"2","key":"36","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1006\/jnth.1996.0081","article-title":"Rational points on Igusa curves and \ud835\udc3f-functions of symmetric representations","volume":"58","author":"Pacheco, Am\u00edlcar","year":"1996","journal-title":"J. Number Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0022-314X","issn-type":"print"},{"issue":"4","key":"37","first-page":"247","article-title":"The canonical lift of an ordinary elliptic curve over a finite field and its point counting","volume":"15","author":"Satoh, Takakazu","year":"2000","journal-title":"J. Ramanujan Math. Soc.","ISSN":"https:\/\/id.crossref.org\/issn\/0970-1249","issn-type":"print"},{"key":"38","unstructured":"R. Schroeppel. Elliptic curves: Twice as fast! Presentation at the CRYPTO 2000 Rump Session, 2000."},{"issue":"6","key":"39","doi-asserted-by":"publisher","first-page":"2599","DOI":"10.1109\/TIT.2009.2018320","article-title":"On the values of Kloosterman sums","volume":"55","author":"Shparlinski, Igor E.","year":"2009","journal-title":"IEEE Trans. Inform. Theory","ISSN":"https:\/\/id.crossref.org\/issn\/0018-9448","issn-type":"print"},{"key":"40","series-title":"Graduate Texts in Mathematics","isbn-type":"print","volume-title":"The arithmetic of elliptic curves","volume":"106","author":"Silverman, Joseph H.","year":"1992","ISBN":"https:\/\/id.crossref.org\/isbn\/0387962034"},{"issue":"3","key":"41","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1007\/BF01459260","article-title":"Kloosterman sums and the \ud835\udc5d-torsion of certain Jacobians","volume":"290","author":"van der Geer, Gerard","year":"1991","journal-title":"Math. Ann.","ISSN":"https:\/\/id.crossref.org\/issn\/0025-5831","issn-type":"print"},{"key":"42","doi-asserted-by":"crossref","unstructured":"F. Vercauteren. Computing zeta functions of curves over finite fields. PhD Thesis. Katholieke Universiteit Leuven, 2003.","DOI":"10.1007\/3-540-45708-9_24"},{"key":"43","series-title":"Discrete Mathematics and its Applications (Boca Raton)","isbn-type":"print","doi-asserted-by":"crossref","DOI":"10.4324\/9780203484029","volume-title":"Elliptic curves","author":"Washington, Lawrence C.","year":"2003","ISBN":"https:\/\/id.crossref.org\/isbn\/1584883650"}],"container-title":["Mathematics of Computation"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.ams.org\/mcom\/2014-83-285\/S0025-5718-2013-02705-6\/S0025-5718-2013-02705-6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"https:\/\/www.ams.org\/mcom\/2014-83-285\/S0025-5718-2013-02705-6\/S0025-5718-2013-02705-6.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T17:44:00Z","timestamp":1776793440000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.ams.org\/mcom\/2014-83-285\/S0025-5718-2013-02705-6\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,5,3]]},"references-count":43,"journal-issue":{"issue":"285","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["S0025-5718-2013-02705-6"],"URL":"https:\/\/doi.org\/10.1090\/s0025-5718-2013-02705-6","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":[[2013,5,3]]}}}