Let $\chi$ be a primitive Dirichlet character of conductor $q$. I want to compute numerically $$G(k)=\sum\_{n\bmod q}\chi(n)e^{2\pi i n(n-k)/(2q)}$$
for all $k$ with $0\le k<2q$ with $k\equiv q\pmod2$ (thanks to this last condition the sum $G(k)$ is well defined). I have two questions:


1. For now I compute these values in a naive way, so using $q\*q$ steps (of course precomputing the $2q$th roots of unity). Is there a better method (even reducing to $q^2/2$ steps would be nice)? Imagine $q=10^5$ or $q=10^6$.
2. When $q$ is not prime, $G(k)$ is often equal to $0$. For instance if $p$ is a prime congruent to $3$ mod 4 dividing $q$ and $k$, it seems that $G(k)=0$, at least for quadratic characters (but I am interested in all characters). My question is: give a necessary and sufficient condition for $G(k)=0$ (sufficient would already be nice).



Computation of modified Gauss sums
For the second question, if $p$ is an odd prime dividing $q$, $p$ divides $k$ with at least the multiplicity with which it divides $q$, and $\chi\_p(-1)=-1$, where $\chi\_p$ is the $p$-adic part of $\chi$, then $G(k)=0$.


This generalizes what you wrote in the $\chi$ quadratic case. In that case, the multiplicity which which $p$ divides $q$ is always one, and $\chi(-1)=-1$ if and only if $p$ is congruent to $3$ mod $4$.


Indeed, the Chinese remainder theorem gives


$$G(k)=\frac{1}{2} \sum\_{n\bmod 2q}\chi(n)e^{2\pi i n(n-k)/(2q)} = \prod\_{ p \mid 2q} \sum\_{n \bmod p^{v\_p(2q)}} \chi\_p (n) e^{ 2 \pi i \lambda\_p n (n-k)/ p^{v\_p(2q)}}$$


where $v\_p(2q)$ denotes the $p$-adic valuation of $2q$, $\lambda\_p$ is the inverse of $q/ p^{v\_p(2q)}$ modulo $p^{v\_p(2q)}$, and $\chi\_p$ is the $p$-adic part of $\chi$.


Fixing on an odd prime $p$, we see that if $k$ is a multiple of $p^{v\_p(2q)}=p^{v\_p(q)}$, the factor at $p$ simplifies to


$$ \sum\_{n \bmod p^{v\_p(2q)}} \chi\_p (n) e^{ 2 \pi i \lambda\_p n^2/ p^{v\_p(2q)}}$$


and if $\chi\_p(-1)= -1$ then the terms for $n$ and $-n$ in the sum always cancel, giving a value of $0$.


If $\chi(-1)= 1$ then we get a sum of two Gauss sums and I don't see any reason it should be zero.


In general, if $v\_p(2q)=1$, the local factor is a nice complete exponential sum. For fixed $k \neq 0$ mod $p$, Katz's equidistribution theory will tell us that the sum is nonzero for a density 1 subset of characters $\chi$. This probably can be proven also for fixed $\chi$ and a density one set of values of $k$, but might be harder to prove (at least by this method - there may be a clever congruence that proves nonvanishing).


