be a prime integer.
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
Based on these hypotheses, we are to design a modular algorithm for
- the product
of these primes exceeds
- every prime
fits in a machine word,
- for all
, the integer
is a power
such that, regarding
, one can compute the product
using the FFT-based algorithm studied in class.
Marc Moreno Maza