You are looking at a specific version 20110425:192651 of this paper. See the latest version.

Paper 2011/199

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.

Note: Comments welcome

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Submitted
Keywords
Kloosterman sumselliptic curvesSylow p-subgroups
Contact author(s)
rgranger @ computing dcu ie
History
2011-04-25: received
Short URL
https://ia.cr/2011/199
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.