## Elements of correction

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

Marc Moreno Maza
2008-03-18