About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Theoretical Computer Science
Paper
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.