An efficient deterministic test for Kloosterman sum zeros

DOI10.1090/S0025-5718-2013-02705-6MaRDI QIDQ2862534zbMATH OpenFDO

Authors Omran Ahmadi, Robert Granger

Publication date 15 November 2013

Published in Mathematics of Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1104.3882

zbMATH Keywords

elliptic curvesSylow \(p\)-subgroupsKloosterman sum zeros

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Curves over finite and local fields (11G20) Gauss and Kloosterman sums; generalizations (11L05) Exponential sums (11T23) Number-theoretic algorithms; complexity (11Y16)

Abstract: We propose a simple deterministic test for deciding whether or not an element $ain{F}_{2^n}^{imes}$ or $F_{3^n}^{imes}$ 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_{2^n}^{imes}$ 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.

Recommendations

• On Kloosterman sums over finite fields of characteristic 3
• On zeros of Kloosterman sums
• On ternary Kloosterman sums modulo 12
• On the Connection between Kloosterman Sums and Elliptic Curves
• scientific article; zbMATH DE number 4148282

Cites work

• scientific article; zbMATH DE number 4148282 (Why is no real title available?)
• scientific article; zbMATH DE number 3937328 (Why is no real title available?)
• scientific article; zbMATH DE number 3510923 (Why is no real title available?)
• scientific article; zbMATH DE number 1349933 (Why is no real title available?)
• scientific article; zbMATH DE number 1936525 (Why is no real title available?)
• scientific article; zbMATH DE number 1942432 (Why is no real title available?)
• scientific article; zbMATH DE number 1504545 (Why is no real title available?)
• scientific article; zbMATH DE number 203033 (Why is no real title available?)
• Binary Kloosterman Sums Modulo 256 and Coefficients of the Characteristic Polynomial
• Binary Kloosterman sums using Stickelberger's theorem and the Gross–Koblitz formula
• Computing the \ell -power torsion of an elliptic curve over a finite field
• Determining the $2$-Sylow subgroup of an elliptic curve over a finite field
• Factoring integers with elliptic curves
• Gauss Sums, Kloosterman Sums, and Monodromy Groups. (AM-116)
• Hyperbent Functions, Kloosterman Sums, and Dickson Polynomials
• Kloosterman sum identities and low-weight codewords in a cyclic code with two zeros
• Kloosterman sums and the p-torsion of certain Jacobians
• Kloosterman sums, elliptic curves, and irreducible polynomials with prescribed trace and norm
• Monomial and quadratic bent functions over the finite fields of odd characteristic
• New Formulae for Efficient Elliptic Curve Arithmetic
• On Integer Values of Kloosterman Sums
• On \(\mathbb{Z}_4\)-linear Goethals codes and Kloosterman sums
• On binary Kloosterman sums divisible by 3
• On the Connection between Kloosterman Sums and Elliptic Curves
• On the Values of Kloosterman Sums
• On the algebraic theory of elliptic modular functions
• On the number of trace-one elements in polynomial bases for \({\mathbb F}_{2^n}\)
• On zeros of Kloosterman sums
• Propagation characteristics of \(x\mapsto x^{-1}\) and Kloosterman sums
• Rational points on Igusa curves and \(L\)-functions of symmetric representations
• Sequences of numbers generated by addition in formal groups and new primality and factorization tests
• Some congruences of Kloosterman sums and their characteristic polynomials
• Ternary Kloosterman sums modulo 18 using Stickelberger's theorem
• The Magma algebra system. I: The user language
• The canonical lift of an ordinary elliptic curve over a finite field and its point counting
• The distribution of the number of points modulo an integer on elliptic curves over finite fields
• The distribution of values of Kloosterman sums
• The divisibility modulo 24 of Kloosterman sums on \(\text{GF}(2^m)\), \(m\) even
• The divisibility modulo 24 of Kloosterman sums on \(\text{GF}(2^m)\), \(m\) odd
• The weights of the orthogonals of the extended quadratic binary Goppa codes

Cited in

(8)

• On zeros of Kloosterman sums
• On the enumeration of irreducible polynomials over \(\mathrm{GF}(q)\) with prescribed coefficients
• A conjecture about Gauss sums and bentness of binomial Boolean functions
• Binary Kloosterman sums with value 4
• On divisibility of exponential sums of polynomials of special type over fields of characteristic 2
• Testing Odd Direct Sums Using High Dimensional Expanders
• On classical Kloosterman sums
• On Kloosterman sums over finite fields of characteristic 3

Describes a project that uses

Uses Software

• Magma

This page was built for publication: An efficient deterministic test for Kloosterman sum zeros

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2862534)