## 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