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?)

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