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.

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.