Exercise 3.

Let and be two non-constant univariate polynomials with variable and with coefficients in for . (In fact, what follows would work with any coefficient ring containing at least 4 elements and where is invertible.) Let , with , be the smallest power of such that and have degree less than , but at least one of them has degree greater than or equal to . (For simplicity, you can assume that and have the same degree and that is a power of .) Hence we can write

 (7)

where are polynomials of degree less than . Let be the product of and . Our goal is to design a fast algorithm for computing . The principle is similar to Karatsuba's trick. However, the construction is a bit more involved and leads to an asymptotically faster algorithm.
(1)
Show that there exist polynomials of degree less than such that we have

Let us regard , , as polynomials in with coefficients in . We denote these polynomials by , , ; they have respective degrees , and . Observe that we have . We evaluate and at , , and . Moreover, we define . Hence we have .
(2)
Show that computing , , , and requires:
• 5 multiplications of polynomials with degree less than ,
• 12 additions or subtractions of polynomials with degree less than ,
• 4 multiplications of a polynomial with degree less than by a power of (actually or ).
(3)
Show that can be computed from , , , , , by solving the following system of linear equations:

 (8)

(4)
Show that solving this linear system can be done in operations in .
Therefore, we have obtained a method for computing the coefficients'' of . This provides, in fact, an algorithm for multiplying univariate polynomials in . Let us estimate its time complexity. Let be the number of operations in that are needed for computing by means of this algorithm.
(5)
Show that satisfies a relation of the form

where is a constant.
(6)
Give an asymptotic upper bound for and compare with the time complexity of Karatsuba's multiplication.