Classification of all the minimal bilinear algorithms for computing the coefficients of the product of two polynomials modulo a polynomial. I: The algebra \(G[u]/<Q(u)^{\ell}>\), \(\ell >1\) (Q1110328)

Let K be a field and let \(r=\sum^{n-1}_{i=0}x_ iu^ i\in K[x_ 0,...,x_{n-1},u]\) and \(s=\sum^{n-1}_{i=0}y_ iu^ i\in K[y_ 0,...,y_{n-1},u]\) be polynomials with indeterminate coefficients. Let h be a polynomial of degree n in K[u]. This paper investigates algorithms for computing \(rs\quad mod h\in K[x_ 1,...,x_{n-1},y_ 1,...,y_{n- 1},u].\) A bilinear algorithm is an algorithm that uses apart from computations in K only multiplications of the form \((\sum^{n- 1}_{i=0}u_ ix_ i)(\sum^{n-1}_{i=0}t_ iy_ i)\). A minimal bilinear algorithm for a given computation uses the least number of such multiplications. In this paper the minimal bilinear algorithms for computing rs mod h in the case that \(h=q^{\ell}\) is given, where q is a monic irreducible polynomial over K and \(\ell >1\). Moreover, they assume that \(\deg (q)>1\). They find that the minimal algorithms all use 2n-1 multiplications of the given form. In all these algorithms one of the following facts is used: \[ rs=rs\quad mod\prod^{2n-2}_{i=0}(u-\alpha_ i)\quad, \] or \[ rs=(rs\quad mod\prod^{2n-2}_{i=1}(u-\beta_ i))+x_{n-1}y_{n- 1}(u-\beta_ i)\quad, \] for certain \(\alpha_ i\) or \(\beta_ i\) in K. These computations are done by using the fact that rs mod (u- \(\alpha)=r(\alpha)s(\alpha).\) The cases that \(\ell =1\) or that h is the product of two relatively prime polynomials is treated before. The case that \(\ell >1\) and \(\deg (q)=1\) will be treated in a forthcomming paper.