1
$\begingroup$

Suppose we have finite field $\mathbb{F}_p$ with prime order $p$. Can we find polynomial in $\mathbb{F}_p[x]$ having given values $a_1, a_2, ... a_n$ at $x=1, 2, ..., n$ in less than $O(n^2)$ operations in $\mathbb{F}_p$?

There is reference to general algorithm in another question which runs in $O(n \log^2 n)$ time, but if I understood correctly, it is not applicable to my case, because it needs $2n$ roots of unity to work (I guess for FFT).

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ This doesn't answer your question, but in some situations we can choose $p$ so it has the desired roots of unity (e.g., by making $p$ a little bigger than necessary), and then the issue doesn't come up. $\endgroup$
    – D.W. ♦
    Commented Jun 21, 2022 at 18:19

0

Reset to default

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.