[Resource Topic] 2011/199: An efficient deterministic test for Kloosterman sum zeros

Welcome to the resource topic for 2011/199

An efficient deterministic test for Kloosterman sum zeros

Authors: Omran Ahmadi, Robert Granger


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.

ePrint: https://eprint.iacr.org/2011/199

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .