Suppose I have a univariate polynomial $p$ over a prime-order finite field $\mathbb{F}_q$ whose roots I know.
Suppose that the roots of $p$ are always an $n$-sized subset of $R=\{1,2,\dots,N\}, N < q$ (or, if it helps, $R = \{\omega^0, \omega^1, \dots,\omega^{N-1}\}$ where $\omega$ is an $N$th primitive root of unity in $\mathbb{F}_q$).
I want to stress that roots are subsets of $R$, and not $R$ itself. For example, the roots could be $\{5,9,13,20,21,22,79\}$.
I know I can interpolate $p$ by starting with monomials for each root as leaves of a binary tree: $(x-5), (x-9), \dots, (x-22), (x-79)$. Then, I can "multiply up the tree recursively" and obtain $p$ as the root of the tree. With FFT-based multiplication, I can do this in $O(n\log^2{n})$ time when I have $n$ roots.
My question: Does there exist an $O(n \log{n})$ algorithm to interpolate $p$ given its roots? I realize that, for particular choices of roots, interpolating $p$ is very fast. For example, $p(x) = x^N - 1$ can be interpolated in $O(N)$ time from its $\{\omega^0, \omega^1, \dots,\omega^{N-1}\}$ roots [1]. However, I am interested in faster algorithms for roots that are arbitrary subsets of $\{\omega^0, \omega^1, \dots,\omega^{N-1}\}$.
I am also aware of the relationship between coefficients and roots, but I don't immediately see how this can be leveraged to get a faster algorithm (e.g., previous question here).
[1]: $O(N)$ time because writing $p$ down requires $O(N)$ space in its uncompressed form.
