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 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$ .
Marc Moreno Maza