An efficient deterministic test for Kloosterman sum zeros

Ahmadi, Omran; Granger, Robert

doi:10.1090/S0025-5718-2013-02705-6

An efficient deterministic test for Kloosterman sum zeros
HTML articles powered by AMS MathViewer

by Omran Ahmadi and Robert Granger PDF

Math. Comp. 83 (2014), 347-363 Request permission

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

Omran Ahmadi and Alfred Menezes, On the number of trace-one elements in polynomial bases for ${\Bbb F}_{2^n}$, Des. Codes Cryptogr. 37 (2005), no. 3, 493–507. MR 2177648, DOI 10.1007/s10623-004-4039-4
K. G. Beauchamp, Walsh functions and their applications, Techniques of Physics, No. 3, Academic Press [Harcourt Brace Jovanovich, Publishers], London-New York, 1975. MR 0462758
I. F. Blake, G. Seroussi, and N. P. Smart, Elliptic curves in cryptography, London Mathematical Society Lecture Note Series, vol. 265, Cambridge University Press, Cambridge, 2000. Reprint of the 1999 original. MR 1771549
Wieb Bosma, John Cannon, and Catherine Playoust, The Magma algebra system. I. The user language, J. Symbolic Comput. 24 (1997), no. 3-4, 235–265. Computational algebra and number theory (London, 1993). MR 1484478, DOI 10.1006/jsco.1996.0125
Wouter Castryck and Hendrik Hubrechts, The distribution of the number of points modulo an integer on elliptic curves over finite fields, Ramanujan J. 30 (2013), no. 2, 223–242. MR 3017927, DOI 10.1007/s11139-012-9444-0
Pascale Charpin and Guang Gong, Hyperbent functions, Kloosterman sums, and Dickson polynomials, IEEE Trans. Inform. Theory 54 (2008), no. 9, 4230–4238. MR 2450780, DOI 10.1109/TIT.2008.928273
Pascale Charpin, Tor Helleseth, and Victor Zinoviev, The divisibility modulo 24 of Kloosterman sums on $\textrm {GF}(2^m)$, $m$ odd, J. Combin. Theory Ser. A 114 (2007), no. 2, 322–338. MR 2293095, DOI 10.1016/j.jcta.2006.06.002
Pascale Charpin, Tor Helleseth, and Victor Zinoviev, Propagation characteristics of $x\mapsto x^{-1}$ and Kloosterman sums, Finite Fields Appl. 13 (2007), no. 2, 366–381. MR 2307134, DOI 10.1016/j.ffa.2005.08.007
D. V. Chudnovsky and G. V. Chudnovsky, Sequences of numbers generated by addition in formal groups and new primality and factorization tests, Adv. in Appl. Math. 7 (1986), no. 4, 385–434. MR 866702, DOI 10.1016/0196-8858(86)90023-0
John Francis Dillon, ELEMENTARY HADAMARD DIFFERENCE-SETS, ProQuest LLC, Ann Arbor, MI, 1974. Thesis (Ph.D.)–University of Maryland, College Park. MR 2624542
Kenny Fong, Darrel Hankerson, Julio Lopez, and Alfred Menezes. Field inversion and point halving revisited. IEEE Transactions on Computers, 53:1047–1059, 2003.
Kseniya Garaschuk and Petr Lisoněk, On binary Kloosterman sums divisible by 3, Des. Codes Cryptogr. 49 (2008), no. 1-3, 347–357. MR 2438461, DOI 10.1007/s10623-008-9171-0
Faruk Göloğlu, Petr Lisoněk, Gary McGuire, and Richard Moloney, Binary Kloosterman sums modulo 256 and coefficients of the characteristic polynomial, IEEE Trans. Inform. Theory 58 (2012), no. 4, 2516–2523. MR 2934081, DOI 10.1109/TIT.2011.2176914
Faruk Göloğlu, Gary McGuire, and Richard Moloney, Ternary Kloosterman sums modulo 18 using Stickelberger’s theorem, Sequences and their applications—SETA 2010, Lecture Notes in Comput. Sci., vol. 6338, Springer, Berlin, 2010, pp. 196–203. MR 2830724, DOI 10.1007/978-3-642-15874-2_{1}6
Faruk Göloğlu, Gary McGuire, and Richard Moloney, Binary Kloosterman sums using Stickelberger’s theorem and the Gross-Koblitz formula, Acta Arith. 148 (2011), no. 3, 269–279. MR 2794931, DOI 10.4064/aa148-3-4
Faruk Göloglu, Gary McGuire, and Richard Moloney. Some congruences of Kloosterman sums and their minimal polynomials. To appear in J. Number Theory.
Tor Helleseth and Alexander Kholosha, Monomial and quadratic bent functions over the finite fields of odd characteristic, IEEE Trans. Inform. Theory 52 (2006), no. 5, 2018–2032. MR 2234462, DOI 10.1109/TIT.2006.872854
Tor Helleseth and Victor Zinoviev, On $Z_4$-linear Goethals codes and Kloosterman sums, Des. Codes Cryptogr. 17 (1999), no. 1-3, 269–288. MR 1715267, DOI 10.1023/A:1026491513009
Huseyin Hisil, Gary Carter, and Ed Dawson, New formulae for efficient elliptic curve arithmetic, Progress in cryptology—INDOCRYPT 2007, Lecture Notes in Comput. Sci., vol. 4859, Springer, Berlin, 2007, pp. 138–151. MR 2570252, DOI 10.1007/978-3-540-77026-8_{1}1
Everett W. Howe, On the group orders of elliptic curves over finite fields, Compositio Math. 85 (1993), no. 2, 229–247. MR 1204781
Jun-ichi Igusa, On the algebraic theory of elliptic modular functions, J. Math. Soc. Japan 20 (1968), 96–106. MR 240103, DOI 10.2969/jmsj/02010096
Nicholas M. Katz, Gauss sums, Kloosterman sums, and monodromy groups, Annals of Mathematics Studies, vol. 116, Princeton University Press, Princeton, NJ, 1988. MR 955052, DOI 10.1515/9781400882120
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 (1989), no. 11, 723–726 (French, with English summary). MR 1054286
Erik Woodward Knudsen, Elliptic scalar multiplication using point halving, Advances in cryptology—ASIACRYPT’99 (Singapore), Lecture Notes in Comput. Sci., vol. 1716, Springer, Berlin, 1999, pp. 135–149. MR 1773226, DOI 10.1007/978-3-540-48000-6_{1}2
Keijo Petteri Kononen, Marko Juhani Rinta-aho, and Keijo O. Väänänen, On integer values of Kloosterman sums, IEEE Trans. Inform. Theory 56 (2010), no. 8, 4011–4013. MR 2752481, DOI 10.1109/TIT.2010.2050806
Gilles Lachaud and Jacques Wolfmann, The weights of the orthogonals of the extended quadratic binary Goppa codes, IEEE Trans. Inform. Theory 36 (1990), no. 3, 686–692. MR 1053865, DOI 10.1109/18.54892
H. W. Lenstra Jr., Factoring integers with elliptic curves, Ann. of Math. (2) 126 (1987), no. 3, 649–673. MR 916721, DOI 10.2307/1971363
Petr Lisoněk, On the connection between Kloosterman sums and elliptic curves, Sequences and their applications—SETA 2008, Lecture Notes in Comput. Sci., vol. 5203, Springer, Berlin, 2008, pp. 182–187. MR 2646401, DOI 10.1007/978-3-540-85912-3_{1}7
Petr Lisoněk and Marko Moisio, On zeros of Kloosterman sums, Des. Codes Cryptogr. 59 (2011), no. 1-3, 223–230. MR 2781611, DOI 10.1007/s10623-010-9457-x
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 (2005), no. 249, 411–427. MR 2085900, DOI 10.1090/S0025-5718-04-01640-0
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 (2009), no. 267, 1767–1786. MR 2501074, DOI 10.1090/S0025-5718-08-02201-1
Marko Moisio, Kloosterman sums, elliptic curves, and irreducible polynomials with prescribed trace and norm, Acta Arith. 132 (2008), no. 4, 329–350. MR 2413356, DOI 10.4064/aa132-4-3
Marko Moisio, The divisibility modulo 24 of Kloosterman sums on $\textrm {GF}(2^m)$, $m$ even, Finite Fields Appl. 15 (2009), no. 2, 174–184. MR 2494333, DOI 10.1016/j.ffa.2008.11.001
Marko Moisio and Kalle Ranto, Kloosterman sum identities and low-weight codewords in a cyclic code with two zeros, Finite Fields Appl. 13 (2007), no. 4, 922–935. MR 2360529, DOI 10.1016/j.ffa.2006.05.002
Harald Niederreiter, The distribution of values of Kloosterman sums, Arch. Math. (Basel) 56 (1991), no. 3, 270–277. MR 1091880, DOI 10.1007/BF01190214
Amílcar Pacheco, Rational points on Igusa curves and $L$-functions of symmetric representations, J. Number Theory 58 (1996), no. 2, 343–360. MR 1393620, DOI 10.1006/jnth.1996.0081
Takakazu Satoh, The canonical lift of an ordinary elliptic curve over a finite field and its point counting, J. Ramanujan Math. Soc. 15 (2000), no. 4, 247–270. MR 1801221
R. Schroeppel. Elliptic curves: Twice as fast! Presentation at the CRYPTO 2000 Rump Session, 2000.
Igor E. Shparlinski, On the values of Kloosterman sums, IEEE Trans. Inform. Theory 55 (2009), no. 6, 2599–2601. MR 2598391, DOI 10.1109/TIT.2009.2018320
Joseph H. Silverman, The arithmetic of elliptic curves, Graduate Texts in Mathematics, vol. 106, Springer-Verlag, New York, 1992. Corrected reprint of the 1986 original. MR 1329092
Gerard van der Geer and Marcel van der Vlugt, Kloosterman sums and the $p$-torsion of certain Jacobians, Math. Ann. 290 (1991), no. 3, 549–563. MR 1116238, DOI 10.1007/BF01459260
F. Vercauteren. Computing zeta functions of curves over finite fields. PhD Thesis. Katholieke Universiteit Leuven, 2003.
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