## The Karatsuba trick

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

 (39)

and

 (40)

COMPUTING THE PRODUCT by the straightforward method requires

• multiplications in and
So the complexity of this computation is (in term of operations 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 .
Hence we can apply the previous formula (for estimating ) with

 (42)

We obtain

 (43)

that is

 (44)

Observe that:

 (45)

Subsections
Marc Moreno Maza
2008-01-07