**Let
be two integers.
Let
be of degree
and let
be monic polynomials
such that the sum of their degrees
is
.
**

**The goal of this exercise is to show that all remainders
can be computed in
operations in
.
**

**The following result (proved in class) will be essential:
division-with-remainder of a polynomial
of degree
by a monic polynomial
of degree
(where
are non-negative integers)
can be done in at most
ring operations in
where we have
**

*
*

2008-03-18