Definition

Multiplying polynomials means multiplying every term of the first polynomial by every term of the second (repeated distribution), then combining like terms; the result has degree equal to the sum of the two factors' degrees, and special patterns like the difference of squares or perfect square trinomial speed up common cases. Formally, for $f = \sum a_ix^i$ and $g = \sum b_jx^j$, the product is $(fg)(x) = \sum_{k} \left(\sum_{i+j=k} a_ib_j\right) x^k$, the Cauchy product (convolution) of the coefficient sequences; fast polynomial multiplication can be done in $O(n \log n)$ time using the Fast Fourier Transform, the basis for fast integer multiplication algorithms.