# Computing coefficients of polynomials from roots in $O(n\log{n})$ time

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.

• It's a bit confusing to use $p$ for both the polynomial and to identify the field. Jun 20, 2019 at 15:44
• Oops. Indeed! Fixed. Jun 20, 2019 at 17:24
• You assume the field $F_q$ is a prime field? Jun 20, 2019 at 22:08
• Yes will update Jun 20, 2019 at 22:09