Classification of all the minimal bilinear algorithms for computing the coefficients of the product of two polynomials modulo a polynomial, part I: The algebra G[u] <Q(u)^l>, l>1

Abstract

In this paper we will classify all the minimal bilinear algorithms for computing the coefficients of (∑ i=0 n-1xiui)( ∑ i=0 n-1yiui) mod Q(u)l where deg Q(u)=j,jl=n and Q(u) is irreducible. The case where l=1 was studied in [1]. For l>1 the main results are that we have to distinguish between two cases: j>1 and j=1. The first case is discussed here while the second is classified in [4]. For j>1 it is shown that up to equivalence every minimal (2n-1 multiplications) bilinear algorithm for computing the coefficients of (∑ i=0 n-1xiui)( ∑ i=0 n-1yiui) mod Q(u)l is done by first computing the coefficients of (∑ i=0 n-1xiui)( ∑ i=0 n-1yiui) and then reducing it modulo Q(u)l (similar to the case l = 1, [1]). © 1988.