The authors consider algorithms for computing the coefficients of completing their previous work [1], which dealt with the same calculation mod Q ( u ) ^l where Q ( u ) is an irreducible monic polynomial of degree greater than one. Complexity of algorithms is measured by the number of multiplications in which both factors involve the indeterminates x _i and y _i ; additions, and multiplications by elements of the ground field G, are not counted. An algorithm is bilinear if in all multiplications the factors are linear and one involves only the x _i and the other only the y _i. Minimal algorithms require 2 n - 1 multiplications. The main result is that every minimal bilinear algorithm for the stated problem is equivalent (in a precisely stated sense) either to a minimal algorithm for computing the product followed by reduction or else to one of two variations on this algorithm.

The authors conjecture that all minimal algorithms are bilinear in the case considered in Part 1 [1], but give a counterexample that is quadratic rather than strictly bilinear for the case considered in Part 2. The arguments are intricate and detailed, but set out in a clear style.