Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



An efficient deterministic test for Kloosterman sum zeros

Authors: Omran Ahmadi and Robert Granger
Journal: Math. Comp. 83 (2014), 347-363
MSC (2010): Primary 11L05; Secondary 11G20, 11T71, 11Y16
Published electronically: May 3, 2013
MathSciNet review: 3120594
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We propose a simple deterministic test for deciding whether or not an element $ a \in \mathbb{F}_{2^n}^{\times }$ or $ \mathbb{F}_{3^n}^{\times }$ 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 $ O(n)$ speedup over the previous fastest test. By repeatedly invoking the test on random elements of $ \mathbb{F}_{2^n}^{\times }$ we obtain the most efficient probabilistic method to date to find non-trivial Kloosterman sum zeros. The analysis depends on the distribution of Sylow $ p$-subgroups in the two families of associated elliptic curves, which we ascertain using a theorem due to Howe.

References [Enhancements On Off] (What's this?)

  • 1. Omran Ahmadi and Alfred Menezes.
    On the number of trace-one elements in polynomial bases for $ {\mathbb{F}}_{2^n}$.
    Des. Codes Cryptogr., 37(3):493-507, 2005. MR 2177648 (2006m:11173)
  • 2. K. G. Beauchamp.
    Walsh functions and their applications.
    Academic Press [Harcourt Brace Jovanovich Publishers], London, 1975.
    Techniques of Physics, No. 3. MR 0462758 (57:2731)
  • 3. I. F. Blake, G. Seroussi, and N. P. Smart.
    Elliptic curves in cryptography, volume 265 of London Mathematical Society Lecture Note Series.
    Cambridge University Press, Cambridge, 2000.
    Reprint of the 1999 original. MR 1771549 (2001i:94048)
  • 4. Wieb Bosma, John Cannon, and Catherine Playoust.
    The Magma algebra system. I. The user language.
    J. Symbolic Comput., 24(3-4):235-265, 1997.
    Computational algebra and number theory (London, 1993). MR 1484478
  • 5. Wouter Castryck and Hendrik Hubrechts.
    The distribution of the number of points modulo an integer on elliptic curves over finite fields.
    Ramanujan J. 30(2):223-242, 2013. MR 3017927
  • 6. Pascale Charpin and Guang Gong.
    Hyperbent functions, Kloosterman sums, and Dickson polynomials.
    IEEE Trans. Inform. Theory, 54(9):4230-4238, 2008. MR 2450780 (2009j:94101)
  • 7. Pascale Charpin, Tor Helleseth, and Victor Zinoviev.
    The divisibility modulo 24 of Kloosterman sums on $ {\rm GF}(2^m)$, $ m$ odd.
    J. Combin. Theory Ser. A, 114(2):322-338, 2007. MR 2293095 (2007k:94089)
  • 8. Pascale Charpin, Tor Helleseth, and Victor Zinoviev.
    Propagation characteristics of $ x \mapsto x^{-1}$ and Kloosterman sums.
    Finite Fields and Their Applications, 13(2):366-381, 2007. MR 2307134 (2008c:11110)
  • 9. D.V Chudnovsky and G.V Chudnovsky.
    Sequences of numbers generated by addition in formal groups and new primality and factorization tests.
    Advances in Applied Mathematics,
    7(4):385-434, 1986. MR 866702 (88h:11094)
  • 10. John. F. Dillon.
    Elementary Hadamard Difference Sets.
    PhD Thesis. University of Maryland, 1974. MR 2624542
  • 11. Kenny Fong, Darrel Hankerson, Julio Lopez, and Alfred Menezes.
    Field inversion and point halving revisited.
    IEEE Transactions on Computers, 53:1047-1059, 2003.
  • 12. Kseniya Garaschuk and Petr Lisoněk.
    On binary Kloosterman sums divisible by 3.
    Des. Codes Cryptogr., 49(1-3):347-357, 2008. MR 2438461 (2010f:94332)
  • 13. F. Göloğlu, P. Lisoněk, G. McGuire, and R. Moloney.
    Binary Kloosterman sums modulo 256 and coefficients of the characteristic polynomial.
    Information Theory, IEEE Transactions on, 58(4):2516-2523, 2012. MR 2934081
  • 14. Faruk Göloglu, Gary McGuire, and Richard Moloney.
    Ternary Kloosterman sums modulo 18 using Stickelberger's theorem.
    In Claude Carlet and Alexander Pott, editors, SETA, volume 6338 of Lecture Notes in Computer Science, pages 196-203. Springer, 2010. MR 2830724
  • 15. Faruk Göloğlu, Gary McGuire, and Richard Moloney.
    Binary Kloosterman sums using Stickelberger's theorem and the Gross-Koblitz formula.
    Acta Arith., 148(3):269-279, 2011. MR 2794931 (2012d:11169)
  • 16. Faruk Göloglu, Gary McGuire, and Richard Moloney.
    Some congruences of Kloosterman sums and their minimal polynomials.
    To appear in J. Number Theory.
  • 17. Tor Helleseth and Alexander Kholosha.
    Monomial and quadratic bent functions over the finite fields of odd characteristic.
    IEEE Transactions on Information Theory, 52(5):2018-2032, 2006. MR 2234462 (2007b:11190)
  • 18. Tor Helleseth and Victor Zinoviev.
    On $ Z_4$-linear Goethals codes and Kloosterman sums.
    Des. Codes Cryptogr., 17(1-3):269-288, 1999. MR 1715267 (2000i:11186)
  • 19. Huseyin Hisil, Gary Carter, and Ed Dawson.
    New formulae for efficient elliptic curve arithmetic.
    In K. Srinathan, C. Rangan, and Moti Yung, editors, Progress in Cryptology â INDOCRYPT 2007, volume 4859 of Lecture Notes in Computer Science, pages 138-151. Springer, Berlin/Heidelberg, 2007. MR 2570252 (2011c:94048)
  • 20. Everett W. Howe.
    On the group orders of elliptic curves over finite fields.
    Compositio Math., 85(2):229-247, 1993. MR 1204781 (94a:11089)
  • 21. Jun-ichi Igusa.
    On the algebraic theory of elliptic modular functions.
    J. Math. Soc. Japan, 20:96-106, 1968. MR 0240103 (39:1457)
  • 22. N. M. Katz.
    Gauss sums, Kloosterman sums, and monodromy groups.
    Princeton Univ. Press, Princeton, NJ, 1988. MR 955052 (91a:11028)
  • 23. Nicholas Katz and Ron Livné.
    Sommes de Kloosterman et courbes elliptiques universelles en caractéristiques $ 2$ et $ 3$.
    C. R. Acad. Sci. Paris Sér. I Math., 309(11):723-726, 1989. MR 1054286 (91e:11066)
  • 24. Erik Woodward Knudsen.
    Elliptic scalar multiplication using point halving.
    In Proceedings of the International Conference on the Theory and Applications of Cryptology and Information Security: Advances in Cryptology, ASIACRYPT '99, pages 135-149, London, UK, 1999. Springer-Verlag. MR 1773226 (2001d:94016)
  • 25. K.P. Kononen, M.J. Rinta-aho, and K.O. Väänänen.
    On integer values of Kloosterman sums.
    Information Theory, IEEE Transactions on, 56(8):4011-4013, aug. 2010. MR 2752481 (2011m:11167)
  • 26. Gilles Lachaud and Jacques Wolfmann.
    The weights of the orthogonals of the extended quadratic binary Goppa codes.
    IEEE Trans. Inform. Theory, 36(3):686-692, 1990. MR 1053865 (92b:94040)
  • 27. H. W. Lenstra, Jr.
    Factoring integers with elliptic curves.
    Ann. of Math. (2), 126(3):649-673, 1987. MR 916721 (89g:11125)
  • 28. Petr Lisoněk.
    On the connection between Kloosterman sums and elliptic curves.
    In Sequences and their applications--SETA 2008, volume 5203 of Lecture Notes in Comput. Sci., pages 182-187. Springer, Berlin, 2008. MR 2646401 (2011m:11168)
  • 29. Petr Lisoněk and Marko Moisio.
    On zeros of Kloosterman sums.
    Designs, Codes and Cryptography, 59:223-230, 2011.
    10.1007/s10623-010-9457-x. MR 2781611 (2012c:11257)
  • 30. J. Miret, R. Moreno, A. Rio, and M. Valls.
    Determining the 2-Sylow subgroup of an elliptic curve over a finite field.
    Math. Comp., 74(249):411-427 (electronic), 2005. MR 2085900 (2005d:11090)
  • 31. J. Miret, R. Moreno, A. Rio, and M. Valls.
    Computing the $ l$-power torsion of an elliptic curve over a finite field.
    Math. Comp., 78(267):1767-1786, 2009. MR 2501074 (2010c:11069)
  • 32. Marko Moisio.
    Kloosterman sums, elliptic curves, and irreducible polynomials with prescribed trace and norm.
    Acta Arith., 132(4):329-350, 2008. MR 2413356 (2009f:11149)
  • 33. Marko Moisio.
    The divisibility modulo 24 of Kloosterman sums on $ {\rm GF}(2^m)$, $ m$ even.
    Finite Fields Appl., 15(2):174-184, 2009. MR 2494333 (2010f:11133)
  • 34. Marko Moisio and Kalle Ranto.
    Kloosterman sum identities and low-weight codewords in a cyclic code with two zeros.
    Finite Fields Appl., 13(4):922-935, 2007. MR 2360529 (2009a:11169)
  • 35. Harald Niederreiter.
    The distribution of values of Kloosterman sums.
    Archiv der Mathematik, 56:270-277, 1991.
    10.1007/BF01190214. MR 1091880 (92b:11057)
  • 36. Amílcar Pacheco.
    Rational points on Igusa curves and $ L$-functions of symmetric representations.
    J. Number Theory, 58(2):343-360, 1996. MR 1393620 (97e:11078)
  • 37. Takakazu Satoh.
    The canonical lift of an ordinary elliptic curve over a finite field and its point counting.
    J. Ramanujan Math. Soc., 15(4):247-270, 2000. MR 1801221 (2001j:11049)
  • 38. R. Schroeppel.
    Elliptic curves: Twice as fast!
    Presentation at the CRYPTO 2000 Rump Session, 2000.
  • 39. Igor Shparlinski.
    On the values of Kloosterman sums.
    IEEE Transactions on Information Theory, 55(6):2599-2601, 2009. MR 2598391 (2011a:11151)
  • 40. Joseph H. Silverman.
    The arithmetic of elliptic curves, volume 106 of Graduate Texts in Mathematics.
    Springer-Verlag, New York, 1992.
    Corrected reprint of the 1986 original. MR 1329092 (95m:11054)
  • 41. Gerard van der Geer and Marcel van der Vlugt.
    Kloosterman sums and the $ p$-torsion of certain Jacobians.
    Math. Ann., 290(3):549-563, 1991. MR 1116238 (92m:11058)
  • 42. F. Vercauteren.
    Computing zeta functions of curves over finite fields.
    PhD Thesis. Katholieke Universiteit Leuven, 2003.
  • 43. Lawrence C. Washington.
    Elliptic curves.
    Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2003.
    Number theory and cryptography. MR 1989729 (2004e:11061)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11L05, 11G20, 11T71, 11Y16

Retrieve articles in all journals with MSC (2010): 11L05, 11G20, 11T71, 11Y16

Additional Information

Omran Ahmadi
Affiliation: Claude Shannon Institute, UCD CASL, University College Dublin, Ireland
Address at time of publication: School of Mathematics, Institute for Research in Fundamental Sciences (IPM), P.O. Box 19395-5746, Tehran, Iran

Robert Granger
Affiliation: Claude Shannon Institute, UCD CASL, University College Dublin, Ireland

Keywords: Kloosterman sum zeros, elliptic curves, Sylow $p$-subgroups
Received by editor(s): April 19, 2011
Received by editor(s) in revised form: February 17, 2012, and April 17, 2012
Published electronically: May 3, 2013
Additional Notes: Both authors were supported by the Claude Shannon Institute, Science Foundation Ireland, Grant No. 06/MI/006.
Article copyright: © Copyright 2013 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society