Polynomial basis

In mathematics, a polynomial basis is 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).[1]

The set of elements of GF(pm) can then be represented as:

using Zech's logarithms.

Addition

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

In GF(2m), 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

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(pm) requires up to m2 multiplications in GF(p) and up to m2 m additions in GF(p).

Some of the methods for reducing these values include:

Squaring

Squaring is an important operation because it can be used for general exponentiation as well as inversion of an element. The most basic way to square an element in the polynomial basis would be to apply a chosen multiplication algorithm on an element twice. In general case, there are minor optimizations that can be made, specifically related to the fact that when multiplying an element by itself, all the bits will be the same. In practice, however, the irreducible polynomial for the field is chosen with very few nonzero coefficients which makes squaring in polynomial basis of GF(2m) much simpler than multiplication.[2]

Inversion

Inversion of elements can be accomplished in many ways, including:

Usage

The polynomial basis is frequently used in cryptographic applications that are based on the discrete logarithm problem such as elliptic curve cryptography.

The advantage of the polynomial basis is that multiplication is relatively easy. For contrast, the normal basis is an alternative to the polynomial basis and it has more complex multiplication but squaring is very simple. Hardware implementations of polynomial basis arithmetic usually consume more power than their normal basis counterparts.

References

  1. Roman, Steven (1995). Field Theory. New York: Springer-Verlag. ISBN 0-387-94407-9.
  2. Huapeng, Wu (2001). "Selected Areas in Cryptography: 7th Annual International Workshop, SAC 2000, Waterloo, Ontario, Canada, August 14–15, 2000,". Springer: 118. |contribution= ignored (help)

See also

This article is issued from Wikipedia - version of the 1/29/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.