Let f, g be two univariate polynomials in x with degrees
p and q respectively.
Let
be their ring of coefficients.
Define
f (x) = apxp + ... + a1x + a0 | (45) |
g(x) = bqxq + ... + b1x + b0. | (46) |
COMPUTING THE PRODUCT f (x)g(x) by the straightforward method requires
Thus the complexity of the computation of the product
of two univariate polynomials of degree at most n
is
(n2) (in term of operations in
).
COMPUTING THE SUM
f (x) + g(x)
is
(n) (in term of operations in
)
if f and g have of degree at most n.
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 f (x)g(x) let's try to save on the number of
multiplications in
.
THE KARATSUBA'S TRICK. Assume f and g have degree (strictly) less than n = 2k (where k is an integer). The Karatsuba's trick computes the product f (x)g(x) as follows.
F1G1 xn + ![]() ![]() |
(47) |
ITS COMPLEXITY.
Let us count how many operations in
we perform with the Karatsuba's trick.
![]() ![]() |
(48) |
T(n) ![]() ![]() |
(49) |
T(n) ![]() ![]() |
(50) |
log2(3) ![]() |
(51) |