** Let
be a prime integer.
Let
and
in
be two polynomials with respective degrees
.
We aim at computing the product
by a fast algorithm.
We consider here the case where
does not divide
.
Hence, there are no
-th primitive roots of unity in
and the FFT-based algorithm studied in class does not apply in this context.
However, we assume that we can find
primes numbers
such that:
**
- the product
of these primes exceeds
,
- every prime
fits in a machine word,
- for all
, the integer
is a power
of
and divides
,
such that, regarding
as polynomials
in
, one can compute the product
in
using the FFT-based algorithm studied in class.

**
Based on these hypotheses, we are to design a modular algorithm for
computing
in
.
**

*Marc Moreno Maza *

2008-03-18