University of Surrey

Test tubes in the lab Research in the ATI Dance Research

An efficient deterministic test for Kloosterman sum zeros

Ahmadi, Omran and Granger, Robert (2013) An efficient deterministic test for Kloosterman sum zeros Mathematics of Computation, 83 (285). pp. 347-363.

RG_MathCompKloo3.pdf - Accepted version Manuscript

Download (263kB) | Preview


We propose a simple deterministic test for deciding whether or not an element a ∈ F×2n or F×3n 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 F×2n we obtain the most efficient probabilistic method to date to find nontrivial 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.

Item Type: Article
Divisions : Faculty of Engineering and Physical Sciences > Computing Science
Authors :
Ahmadi, Omran
Date : 3 May 2013
DOI : 10.1090/S0025-5718-2013-02705-6
Uncontrolled Keywords : Kloosterman sum zeros; Elliptic curves; Sylow $p$-subgroups
Depositing User : Clive Harris
Date Deposited : 06 Feb 2019 15:50
Last Modified : 17 Apr 2019 09:09

Actions (login required)

View Item View Item


Downloads per month over past year

Information about this web site

© The University of Surrey, Guildford, Surrey, GU2 7XH, United Kingdom.
+44 (0)1483 300800