15
$\begingroup$

Given $n$ roots, $x_1, x_2, \dotsc, x_n$, the corresponding monic polynomial is

$$y = (x-x_1)(x-x_2)\dotsm(x-x_n) = \prod_{i}^n (x - x_i)$$

To get the coefficients, i.e., $y = \sum_{i}^n a_i x^i$, a straightforward expansion requires $O \left(n^2\right)$ steps.

Alternatively, if $x_1, x_2, \dotsc, x_n$ are distinct, the problem is equivalent to polynomial interpolation with $n$ points: $(x_1, 0), (x_2, 0), \dotsc, (x_n, 0)$. The fast polynomial interpolation algorithm can be run in $O \left( n \log^2(n) \right)$ time.

I want to ask whether there is any more efficient algorithm better than $O \left(n^2\right)$? Even if there are duplicated values among $\{x_i\}$? If it helps, we can assume that the polynomial is over some prime finite field, i.e., $x_i \in \mathbf{F}_q$.

$\endgroup$

2 Answers 2

25
$\begingroup$

This can be done in $O(n \log^2 n)$ time, even if the $x_i$ have duplicates, via the following divide-and-conquer method.

First compute the coefficients of the polynomial $f_0(x)=(x-x_1) \cdots (x-x_{n/2})$ (via a recursive call to this algorithm). Then compute the coefficients of the polynomial $f_1(x)=(x-x_{n/2+1})\cdots(x-x_n)$. Next, compute the coefficients of $f(x)=f_0(x)f_1(x)$ using FFT-based polynomial multiplication.

This yields an algorithm whose running time satisfies the recurrence

$$T(n) = 2 T(n/2) + O(n \log n).$$

The solution to this recurrence is $T(n) = O(n \log^2 n)$. This all works even if there are duplicates in the $x_i$.

(You might also be interested in Multi-point evaluations of a polynomial mod p.)

$\endgroup$
3
  • $\begingroup$ Isn't FFT using approximate arithmetic, so in case of finite fields not really usable, because round errors eventually will lead to wrong result? Or I am missing something? $\endgroup$
    – Somnium
    Jun 21 at 16:49
  • $\begingroup$ @Somnium, No. I can't explain in a comment, but it sounds like you are basically doubting whether it is possible to multiply polynomials in $O(n \log n)$ time. If so, I suggest reading about FFT-based polynomial multiplication, and then if you have a specific question, ask a new question about it. FFT/DFT over a finite field uses exact arithmetic (no approximations). See en.wikipedia.org/wiki/…, en.wikipedia.org/wiki/…. $\endgroup$
    – D.W.
    Jun 21 at 17:36
  • $\begingroup$ Thanks! I only saw FFT with real (complex) numbers which used sine and cosine functions which cannot be represented exactly. Perhaps I was reading irrelevant search results. I will follow your advice. $\endgroup$
    – Somnium
    Jun 21 at 20:36
2
$\begingroup$

You should also look at what you actually want to achieve. The coefficients can grow very quickly, meaning that evaluating the polynomial can have large rounding errors. Given the roots, you can evaluate the polynomial quite quickly without knowing the coefficients, and with high precision.

$\endgroup$
1
  • 5
    $\begingroup$ Thanks for the comments. This is not a problem for me as the polynomial is over some prime finite field $\mathbf{F}_q$. This task (expanding a polynomial given its roots) is quite common in set accumulator or zero-knowledge proof in the cryptographic settings. $\endgroup$
    – xucheng
    Nov 4, 2019 at 10:30

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.