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$ – Robert Israel Jun 20 '19 at 15:44
  • $\begingroup$ Oops. Indeed! Fixed. $\endgroup$ – Alin Tomescu Jun 20 '19 at 17:24
  • $\begingroup$ You assume the field $F_q$ is a prime field? $\endgroup$ – kodlu Jun 20 '19 at 22:08
  • $\begingroup$ Yes will update $\endgroup$ – Alin Tomescu Jun 20 '19 at 22:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.