(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

- (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 .

- (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.

2008-01-31