Polynomial basis

In mathematics, a polynomial basis is a basis of a polynomial ring, viewed as a vector space over the field of coefficients, or as a free module over the ring of coefficients. The most common polynomial basis is the monomial basis consisting of all monomials. Other useful polynomial bases are the Bernstein basis and the various sequences of orthogonal polynomials.

In the case of a finite extension of a finite fields, polynomial basis may also refer to a basis of the extension of the form

where α is the root of a primitive polynomial of degree m equal of the degree of the extension).

The set of elements of GF(p^m) can then be represented as:

using Zech's logarithms.

Addition using the polynomial basis is as simple as addition modulo p. For example, in GF(3^m):

In GF(2^m), addition is especially easy, since addition and subtraction modulo 2 are the same thing (so like terms "cancel out"), and furthermore this operation can be done in hardware using the basic XOR logic gate.

Multiplication of two elements in the polynomial basis can be accomplished in the normal way of multiplication, but there are a number of ways to speed up multiplication, especially in hardware. Using the straightforward method to multiply two elements in GF(p^m) requires up to m² multiplications in GF(p) and up to m² − m additions in GF(p).

Some of the methods for reducing these values include:

...
Wikipedia