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:
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$.
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).