Lagrange interpolation on a Galois Field in time $O(n \log (n))$

Question

I have the values of a polynomial $p(x)$ defined on the Galois field mod $p$ (with $p$ prime) at the points zero to around two million. I need an algorithm to find the coefficients of the original polynomial $p(x)$ in time $O(n \log (n))$, as $O(n^2)$ is way too slow for this application. In Chapter 3 of Pan's Structured Matrices and Polynomials there is an algorithm, but it is stated that $|t_i| = 1$ for all $i$, which is not the case here. Is there any other alternative?