- Define
in
. Assume that
and
have degree
and define:
![$\displaystyle f = f_d x^d + \cdots + f_1 x + f_0 \ \ {\rm and} \ \ g = g_d x^d + \cdots + g_1 x + g_0.$](img80.png) |
(18) |
Then define:
![$\displaystyle h = c_{2d} x^{2d} + \cdots + c_1 x + c_0.$](img81.png) |
(19) |
For all
, we have:
![$\displaystyle c_k = {\sum}_{i+j=k} \, f_i g_j.$](img83.png) |
(20) |
Observe that, for a given
in the range
,
the number of products
is at most
.
Indeed, the polynomials
and
have
terms.
From there, we deduce that for all
, we have:
![$\displaystyle \mid c_k \mid \ \leq \ (d+1) B^2.$](img88.png) |
(21) |
- One can proceed as follows:
- Let
machine-word-size
odd primes such that their product
exceeds
- For all
compute
- the images
and
of
and
in
,
- the product
in
.
- Using the Chinese Remaindering Algorithm coefficient-wise,
reconstruct
from
.
- We give complexity estimates (upper bounds for the number of machine-word
operations) for each of the steps
,
and
above.
For the operations on integers, we use bounds based on classical
quadratic algorithms (not fast ones, since they were not discussed
in class).
Let
be the length of a machine-word, let
be the number of machine-words to write
and let
to write
.
-
machine-word operations
-
machine-word operations
-
machine-word operations
Marc Moreno Maza
2008-03-18