## 8.2 COOK-TOOM ALGORITHM

The Cook-Toom algorithm is a linear convolution algorithm for polynomial multiplication. It is based on the *Lagrange interpolation theorem.* The Lagrange interpolation theorem states that,

“Let *β*_{0}, … , *β*_{n} be a set of *n* + 1 distinct points, and let *f*(*β*_{i}), for *i* = 0, 1, … , *n* be given. There is *exactly* one polynomial *f*(*p*) of degree *n* or less that has value *f*(*β*_{i}) when evaluated at *β*_{i} for *i* = 0, 1, … , *n.* It is given by

Consider an *N*-point sequence *h* = {*h*_{0}, *h*1, … , *h*_{N−1}} and an *L*-point sequence *x* = {*x*_{0}, *x*_{1}, … , *x*_{L−1}}. The linear convolution of *h* and *x* can be expressed in terms of polynomial multiplication as follows:

where *h*(*p*) = *h*_{N−1}*p*^{N−1} + · · · + *h*_{1}*p* + *h*_{0}, *x*(*p*) = *x*_{L−1}p^{L−1} + · · · + *x*_{1}*p* + *x*_{0} and *s*(*p*) = *s* _{L + N−2}P^{L+N−2} + · · · + *s*_{1}p + s_{0}. The output polynomial *s*(*p*) has degree *L* + *N* – 2 and has *L* + *N* – 1 different coefficients. Therefore, it can be uniquely determined by its values at *L* + *N* − 1 different points. Let *β*_{0},*β*_{1}, … ,*β*_{L+N−2} be *L* + *N* − 1 different real numbers. If *s*(*β*_{i}), for *i* = 0, 1, … , *L* + *N* − 2 are known, *s*(*p*) can be computed using the Lagrange interpolation theorem as

It can be proved that (8.5) is the unique solution for *s*(*p*) given the values of ...