** **

**Algorithm 3**
*
*

**Theorem 3**
*Let
be a commutative ring with identity element.
Let
and
be univariate polynomials over
with respective degrees
and
such that
and
monic.
Algorithm 3
computes the quotient and the remainder of
w.r.t.
in
operations in
*

**Remark 7**
*If several divisions by a given
needs to be performed
then we may precompute the inverse of
modulo some powers
of
.
Assuming that
possesses suitable primitive roots of unity,
we can also save their DTF.
*

**Remark 8**
*In Theorem 3,
the complexity estimate becomes
if the **middle product* technique
described in Remark 6
applies.
Moreover, if
holds, the
can be repalced by
.

*Marc Moreno Maza *

2008-01-07