- Define
in
. Assume that
and
have degree
and define:
(18)

Then define:(19)

For all , we have:(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:(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

*
*

2008-03-18