An efficient deterministic test for Kloosterman sum zeros

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

2011-04-19

arxiv.org/abs/1104.3882v2

Mathematics

Number Theory

17 pages, accepted to Mathematics of Computation. This is the final version with many improvements upon the first version. We

Scientific paper

We propose a simple deterministic test for deciding whether or not an element $a \in \F_{2^n}^{\times}$ or $\F_{3^n}^{\times}$ 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}^{\times}$ 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.

Affiliated with

Also associated with

No associations

Rating

An efficient deterministic test for Kloosterman sum zeros does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An efficient deterministic test for Kloosterman sum zeros, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An efficient deterministic test for Kloosterman sum zeros will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-431621