Gauss Sums: Finding the Root of Unity
- Date: 04/19/2007
Bernhard Schmidt (Nanyang Technological University)
University of Calgary
A Gauss sum over a finite field GF(q) is a sum of q algebraic numbers.
It is often useful to evaluate Gauss sums explicitly, for instance, in
coding theoretic or cryptographic applications. For small q, the
evaluation of Gauss sums can be done naively by summing up all terms.
For large q, this is impossible, but in many cases the LLL algorithm
can be used to compute Gauss sums up to multiplication with a root of
unity. However, finding the exact root of unity is surprisingly
difficult. A special case of this problem is well known: the
determination of the sign of quadratic Gauss sums is a notorious,
difficult problem which was solved by Gauss in 1805. We will describe a
method to find the exact root of unity for all Gauss sums over finite
fields under the condition that the values of the Gauss sums are known
up to multiplication with a root of unity.
10th Anniversary Speaker Series 2007