Statement

Let $ p > 2$ be a prime integer. Let $ f$ and $ g$ in $ {\mbox{${\mathbb{Z}}$}}/p{\mbox{${\mathbb{Z}}$}}[x]$ be two polynomials with respective degrees $ m \geq n > 0$ . We aim at computing the product $ f \, g$ by a fast algorithm. We consider here the case where $ m+n+1$ does not divide $ p-1$ . Hence, there are no $ (n+m+1)$ -th primitive roots of unity in $ {\mbox{${\mathbb{Z}}$}}/p{\mbox{${\mathbb{Z}}$}}$ and the FFT-based algorithm studied in class does not apply in this context. However, we assume that we can find $ r$ primes numbers $ 2 < p_1 < \cdots < p_r$ such that: Based on this hypothesis, we are to design a modular algorithm for computing $ fg$ in $ {\mbox{${\mathbb{Z}}$}}/p{\mbox{${\mathbb{Z}}$}}[x]$ .

Marc Moreno Maza
2008-03-18