** Let
be a field and let
be a polynomial of degree
.
We aim at computing in
as fast
as possible.
Let
be another polynomial with degree
strictly less than
and such that
and
are relatively prime.
Let
such that
**

**
We consider the application
from
to itself
mapping
to
.
We shall see that
can be computed in
operations in
for a suitable choice of
.
For
define
and
.
Then,
**
- define
.
- let
be the quotient-and-remainder
in the division of
by
,
- let
be the quotient-and-remainder
in the division of
by
,
- let

*Marc Moreno Maza *

2008-03-18