Statement

We saw in class that Karatsuba's trick can reduce the cost of multiplying two univariate polynomials. This trick splits each input polynomial in two parts: its low degree terms and high degree terms. It is natural to ask whether there is a similar trick

• which splits each input polynomial into three parts, and
• which leads to a time complexity improvement in computing their product.

To make things simple, let us restrict ourselves to two polynomials $A = a_n X^n + \cdots + a_0$ and $B = b_n X^n + \cdots + b_0$ with the same degree $n$ and let us assume that $n$ is a power of $3$ .