Some bilinear forms whose multiplicative complexity depends on the field of constants

Abstract

In this paper we consider the system of bilinear forms which are defined by a product of two polynomials modulo a third P. We show that the number of multiplications depend on how the field of constants used in the algorithm splits P. If {Mathematical expression} then 2 ·deg (P) - k multiplications are needed. (We assume that Pi is irreducible.) © 1977 Springer-Verlag New York Inc.