On multiplication in algebraic extension fields

Abstract

In this paper we characterize all algorithms for obtaining the coefficients of (Σn-1i=0 xiui)(Σn-1i=0 yiui) mod P(u), where P(u) is an irreducible po lynomial of degree n, which use 2n - 1 multiplications. It is shown that up to equivalence, all such algorithms are obtainable by first obtaining the coefficients of the product of two polynomials, and then reducing modulo the irreducible polynomial. © 1979.