I am working in a finite prime field $\mathbb{F}_p$ that does not have primitive $n$-th roots of unity for any large smooth integer $n$, which makes FFTs a bit difficult.

If I need to compute a product of linear polynomials $\prod\limits_{i=0}^n (X+a_i)$, can I do so in runtime $O(n\cdot \log^2(n))$?

How bad is the slowdown if I try to use FFTs in a field without all the n-th roots of unity? Do I need to pass to the smallest field extension of $\mathbb{F}_p$ that does contain a primitive $n$-th root in order to compute the product in sub-quadratic runtime?

  • 1
    $\begingroup$ You mentioned field extensions... This is just a shot in the dark, but if you can adjoin values to $\mathbb{F}_p$ to get $\mathbb{F}_{p^k}$, you can use the Frobenius transform which runs in $(n \log{n}) / k$, even faster than the FFT. $\endgroup$
    – Matt Groff
    Commented May 26, 2022 at 3:43


Your Answer

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