**Let
be two univariate polynomials in
with degrees
and
respectively.
Let
be their ring of coefficients.
Define
**

(39) |

(40) |

**COMPUTING THE PRODUCT
by the straightforward method requires
**

- multiplications in and
- additions in .

**Thus the complexity of the computation of the product
of two univariate polynomials of degree at most
is
(in term of operations in
).
**

**COMPUTING THE SUM
is
(in term of operations in
)
if
and
have of degree at most
.
**

*
*

*
*

**ADDING IS OFTEN CHEAPER THAN MULTIPLYING.
So adding polynomials is cheaper than multiplying them.
For many rings
addition is also cheaper than multiplication.
So when computing
let's try to save on the number of
multiplications in
.
**

*
*

*
*

**THE KARATSUBA'S TRICK.
Assume
and
have degree
(strictly) less than
(where
is an integer).
The Karatsuba's trick computes the product
as follows.
**

- If then compute the element of .
- Define and where have degree .
- Compute , , recursively
- Return
(41)

*
*

*
*

**ITS COMPLEXITY.
Let us count how many operations in
we perform with the Karatsuba's trick.
**

- At step we perform at most additions to compute and .
- At step we perform at most subtractions to compute
- At step we perform at most additions to add this latter polynomial to .

(42) |

(43) |

(44) |

(45) |

*
*

*
*

2008-01-07