Gauss Sums: Finding the Root of Unity

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.