4
$\begingroup$

Let $F$ be a prime finite field. Let $d$ be a power of two dividing $p-1$. Suppose I have $d$ pairs of univariate polynomials $f_i,g_i$ over $F$ for $i=1,\ldots,d$. All have degree less than $d$. I want to compute the coefficients of the polynomial

$$h(X)\triangleq \sum_{i=1}^d f_i(X) g_i(X) $$

I can do this in $O(d^2\cdot \log d)$ operations by computing each product using FFT techniques in time $O(d\log d)$ and then summing the $d$ products.

Can I do this in time $O(d^2)$ somehow? Is there an indication that would contradict some conjectured lower bound?

I don't mind computing $h$ in any basis, doesn't have to be the monomial basis.

Improve this question
$\endgroup$
1
  • $\begingroup$ A very brief remark: Restating your problem as the inner product of two vectors of polynomials, it is clear that a $O(d^2)$ algorithm implies a $O(d^3)$ algorithm for matrix-vector product with polynomial matrices. I cannot find a reference where it is explicitly written, but all the complexity results I know of for polynomial matrices use FFT-based techniques, and thus have the $\log d$ factor in the complexity. Cf for instance this recent paper for references. Of course, I do not claim any lower bound though... $\endgroup$
    – Bruno
    Feb 5, 2021 at 18:06

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.