Classification of all the minimal bilinear algorithms for computing the coefficients of the product of two polynomials modulo a polynomial. Part II: The algebra G[u]/〈uⁿ〉

Abstract

In this paper we classify all the minimal bilinear algorithms for computing the coefficients of (Σn-1i=0 xiui) (Σn-1i=0 yiui) mod Q(u)l where deg Q(u)=j, jl=n and Q(u) is irreducible (over G) is studied. The case where l = 1 was studied in [8]. For l > 1 the main results are that we have to distinguish between two cases: j > 1 and j = 1. The case where j > 1 was studied in [1]. For j = 1 it is shown that up to equivalence, every minimal (2n - 1 multiplications) bilinear algorithm for computing the coefficients of (Σn-1i=0 xiui) (Σn-1i=0 yiui) mod un is done either by first computing the coefficients of (Σn-1i=0 xiui) (Σn-1i=0 yiui) and then reducing them modulo un or by first computing the coefficients (Σn-2i=0 xiui) (Σn-1i=0 yiui) and then reducing them modulo un and adding xn-1y0un-1 or by first computing the coefficients (Σn-2i=0 xiui) (Σn-2i=0 yiui) and then reducing them modulo un and adding (xn-1y0 + x0yn-1)un-1. © 1991.