How fast can we numerically calculate Kloosterman sums?

Question

Define the usual Kloosterman sum by $$S(m,n;c) = \sum_{\substack{x \pmod{c} \\ (x,c) = 1}} e\Big(\frac{mx + n\overline{x}}{c}\Big),$$ where $x \overline{x} \equiv 1 \pmod{c}$, and $e(x) = e^{2 \pi i x}$. I'm interested in knowing if there is a faster way to calculate values of this rather than just adding up the $\varphi(c) \leq c$ values of the sum. By calculate here, I just mean to find a good numerical approximation; the definition already gives an exact expression for it as an element of $\mathbb{Z}[e^{2\pi i/c}]$ which probably can't be improved by much in general. I'm interested in $m$ and $n$ fixed, and how fast it can be computed in terms of $c$. The case $c=$prime is probably the most interesting. I'd also be interested to know if people have considered the speed of evaluation of the full list of values of $S(m,n;c)$ for $c \leq C$.

For the case of a Gauss sum to modulus $q$, I have heard that it is "well-known" how to calculate it in around $\sqrt{q}$ steps as follows. The main point is to use the fact that the completed Dirichlet $L$-function has the approximate functional equation (See Theorem 5.3 of Iwaniec and Kowalski's book) $$L(1/2, \chi) = \sum_{n} \frac{\chi(n)}{\sqrt{n}} V(\frac{n}{X \sqrt{q}}) + \epsilon(\chi) \sum_{n} \frac{\overline{\chi}(n)}{\sqrt{n}} V(nX/\sqrt{q}).$$ Here $V$ is a special function that in practice can be calculated (e.g. in Mike Rubinstein's Lcalc package), $\epsilon(\chi) = i^{-a} \tau(\chi) q^{-1/2}$ where $a$ is $0$ or $1$ if $\chi$ is even or odd, $\tau(\chi)$ is the Gauss sum, and $X> 0$ is a parameter to choose. Write this in the form $L(1/2, \chi) = A(X) + \epsilon(\chi)B(X)$. Taking say $X=1$ and another value of $X$ close to $1$ will give different values for $A(X)$ and $B(X)$, and so one can solve for $\epsilon(\chi)$. The function $V(x)$ has rapid decay for $x \gg 1$, so it takes around $\sqrt{q}$ terms in the sum to evaluate $A(X)$ and $B(X)$, far fewer than the full $q$ terms needed to evaluate the Gauss sum by definition.

Answer 1

This is not quite an answer to your interesting question, but rather a couple of related comments. First your nice "well known" observation on the Gauss sum can perhaps be expressed more simply by noting that if $\chi(-1)=1$ then Poisson summation gives $$ \tau(\overline{\chi}) \sum_{-\infty}^{\infty} \chi(n) e^{-\pi n^2/q} = \sqrt{q} \sum_{-\infty}^{\infty} \overline{\chi}(n) e^{-\pi n^2/q}, $$ so that about $\sqrt{q}$ terms are needed to approximate $\tau(\chi)$. A similar argument of course holds if $\chi(-1)=-1$, and in any case this is closely related to what you wrote.

Secondly, one can consider a different related problem: namely rapid algorithms for counting points on curves over finite fields. For elliptic curves there is a rapid algorithm of Schoof which allows this in polynomial time, but for general curves I don't think an algorithm faster than the naive one is known. One survey is Elkies http://www.math.harvard.edu/~elkies/modular.pdf but this is now twenty years old so perhaps much more is known. Schoof's algorithm is useful in computing Kloosterman sums over large finite fields of characteristic two or three: see work of Lisonek and others on this topic http://link.springer.com/chapter/10.1007%2F978-3-540-85912-3_17

The above is somewhat orthogonal to the problem you have in mind. My only other thought was to try to use divisor function in arithmetic progressions to compute Kloosterman sums, but I did not obtain anything nontrivial.