Let
and
be two univariate polynomials in
.
We assume that
is **monic** and has degree
and that
has degree
whith
.
We define
and
.
We are interesting in computing the remainder
of the Euclidean division of
by
(regarding them
as polynomials in
), by a modular method.
Let
be a prime number and
be the application that
maps every integer
with its residue class
in
.
We extend this application to a map denoted
again,
from
to
, such that
is mapped to
.
- Explain why the remainder
belongs to
, that is
no fractions appears during the computations.
- Consider
and
. Compute
and
.
- Consider
. Compute
and
.
Then compute the quotient and the remainder of
by
.
- In the general case, what is the relation between
and the remainder
of
by
?
- Design a modular method to compute
.

**Answer 4**
*
*

**Answer 5**
*
*

*Marc Moreno Maza *

2008-01-31