** 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
and
with the same degree
and let us assume that
is a power of
.
**
*Marc Moreno Maza *

2008-03-18