# Complexity class of phase information in Gauss sum

Have number theoretic functions such as Gauss sums been studied from a complexity view point? Where can I get a good introduction into complexity of Gauss sum estimation (beyond the quadratic case)?

Actually I was looking for something more than the answers given. It is known Gauss sums have a random walk behavior than is exploited in designing low-correlation sequences. Also Montogomery's conjecture provides a tighter bound than the Weil bounds of Deligne under the assumption of random behavior (deeper exposition in the book by Katz and Sarnak - the material of which I am not familiar). I was actually curious whether such randomness has been utilized in computer science. It seems very possible there are uses.

• You are now asking a quite different question... – Martin Schwarz Jul 27 '11 at 9:49
• @Martin I thought the questions are related? – v s Jul 27 '11 at 16:00
• @Martin I think some complexity classes do include randomness in their definitions. – v s Jul 28 '11 at 2:18