Classification of all the minimal bilinear algorithms for computing the coefficients of the product of two polynomials modulo a polynomial. II: The algebra \(G[u]/\langle{} u^ n \rangle\) (Q1178708)

This paper deals with the classification of all minimal bilinear algorithms for the computation of a product of polynomials modulo another polynomial \(R\). As a consequence of the Chinese remainder theorem it is only interesting to consider the case that \(R=Q^ \ell\) is a power of an irreducible polynomial \(Q\). The case that \(\ell=1\) was already treated by \textit{S. Winograd} [Theor. Comput. Sci. 8, 337-359 (1979; Zbl 0404.12016)]. The case that \(\ell>1\) and \(\deg(Q)>1\) was treated in the first part of the paper [\textit{A. Averbuch}, \textit{Z. Galil} and \textit{S. Winograd}, Theor. Comput. Sci. 58, 17-56 (1988; Zbl 0656.68040)]. In this part the final case \(\ell>1\) and \(\deg(Q)=1\) is treated. A minimal algorithm for computing the product of two polynomials modulo \(u^ n\) needs \(2n-1\) multiplications. Together with the results of the above mentioned papers it is shown that each minimal algorithm needs first to compute the coefficients of the product after which reduction is being done, hence large coefficients will appear during the computation.