**An efficient deterministic test for Kloosterman sum zeros**

*Omran Ahmadi and Robert Granger*

**Abstract: **We propose a simple deterministic test for deciding whether or not a non-zero element $a \in \F_{2^n}$ or $\F_{3^n}$ is a zero of the corresponding Kloosterman sum over these fields, and analyse its complexity. The test seems to have been overlooked in the literature.
For binary fields, the test has an expected operation count
dominated by just two $\F_{2^n}$-multiplications when $n$ is odd (with
a slightly higher cost for even extension degrees), making its repeated
invocation the most efficient method to date to find a non-trivial
Kloosterman sum zero in these fields. The analysis depends on the distribution of Sylow $p$-subgroups in two corresponding families of elliptic curves, which we prove using a theorem due to Howe.

**Category / Keywords: **secret-key cryptography / Kloosterman sums, elliptic curves, Sylow p-subgroups

**Publication Info: **Submitted

**Date: **received 19 Apr 2011

**Contact author: **rgranger at computing dcu ie

**Available format(s): **PDF | BibTeX Citation

**Note: **Comments welcome

**Version: **20110425:192651 (All versions of this report)

**Short URL: **ia.cr/2011/199

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]