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
with the same degree
and let us assume that
is a power of
Marc Moreno Maza
- which splits each input polynomial into three parts, and
- which leads to a time complexity improvement
in computing their product.