Multi-point evaluations of a polynomial mod p
No, $O(n \lg q)$ running time is not achievable.  It takes $\Omega(q)$ space even just to write out the answer, so any algorithm will necessarily have running time at least $\Omega(q)$.

However, you can find algorithms that are more efficient than the naive solution.  The naive solution for evaluating a polynomial of degree $n$ at $q$ points takes $O(nq)$ time, by using Horner's rule $q$ times.  It turns out there are faster algorithms to do this, namely, in $O(\max(n,q) \log^2 \max(n,q))$ time.  For simplicity of exposition, let me assume $q=n$, so the goal is to evaluate the polynomial $f(x)$ at points $x_1,\dots,x_n$.

We're going to use divide-and-conquer.  Define

$$\begin{align*}
f_0(x) &amp;= f(x) \bmod (x-x_1)(x-x_2)\cdots(x-x_{n/2})\\
f_1(x) &amp;= f(x) \bmod (x-x_{n/2+1})\cdots(x-x_n)
\end{align*}$$

Now we have

$$f(x_i) = \begin{cases}
f_0(x_i) &amp;\text{if }i\le n/2\\
f_1(x_i) &amp;\text{otherwise.}\end{cases}$$

Thus, it suffices to evaluate $f_0(x)$ at the points $x_1,\dots,x_{n/2}$ and evaluate $f_1(x)$ at the points $x_{n/2+1},\dots,x_n$.  We can do this by a recursive invocation of the same procedure.  Since both $f_0(x)$ and $f_1(x)$ have degree at most $n/2$, we're invoking the procedure recursively on two subproblems of size $n/2$.

This requires us compute $f_0(x)$ and $f_1(x)$ from $f(x)$.  This can be done in $O(n \log n)$ time, using FFT-based polynomial division, which works similar to FFT-based polynomial multiplication (see here, here, and these slides).

The running time of this divide-and-conquer algorithm is

$$T(n) = 2 T(n/2) + O(n \log n),$$

which has the solution $T(n) = O(n \log^2 n)$.  Thus, you can evaluate a polynomial of degree $n$ at $n$ arbitrary points in $O(n \log^2 n)$ time.

Since you are working modulo $p$, you want to use a Discrete Fourier Transform designed for mod $p$ arithmetic. 

Thanks to Niklas B. for pointing me to http://www.dis.uniroma1.it/~sankowski/lecture4.pdf.