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:

• the product $m$ of these primes exceeds $C = (n+1) (\frac{p-1}{2})^2$ ,
• every prime $p_1, \ldots, p_r$ fits in a machine word,
• for all $i = 1, \ldots, r$ , the integer $m+n+1$ divides $p_i -1$ , such that, regarding $f \, g$ as polynomials in ${\mbox{${\mathbb{Z}}$}}/p_i{\mbox{${\mathbb{Z}}$}}[x]$ , one can compute the product $fg$ in ${\mbox{${\mathbb{Z}}$}}/p_i{\mbox{${\mathbb{Z}}$}}[x]$ using the FFT-based algorithm studied in class.

Based on this hypothesis, we are to design a modular algorithm for computing $fg$ in ${\mbox{${\mathbb{Z}}$}}/p{\mbox{${\mathbb{Z}}$}}[x]$ .