Statement

Let $f$ and $g$ in ${\mbox{${\mathbb{Z}}$}}[x]$ be two polynomials of degree at most $d > 0$ . Let $B$ be an upper bound for the absolute value of a coefficient in $f$ or $g$ . Then $C = (d+1) B^2$ is an upper bound for the absolute value of a coefficient in the product $fg$ . We assume that we have $r$ primes numbers $2 < p_1 < \cdots < p_r$ such that their product $m$ exceeds $2 C$ In addition, we assume that

• every prime $p_1, \ldots, p_r$ fits in a machine word,
• computing the $fg$ mod $p_i$ , for all $i = 1, \ldots, r$ , can be done $O(d \, {\log}(d) {\log}{\log}(d))$ machine word operations.