Polynomial basis


Polynomial basis

In mathematics, the polynomial basis is a basis for finite extensions of finite fields.

Let α ∈ GF("p""m") be the root of a primitive polynomial of degree "m" over GF("p"). The polynomial basis of GF("p""m") is then

:{ 0, 1, alpha, ldots, alpha^{m-1}}

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

:{ 0, 1, alpha, alpha^2, ldots, alpha^{p^{m-2 }

using Zech's logarithms.

Addition

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

:(2alpha^2 + 2alpha + 1) + (2alpha + 2) = 2alpha^2 + 4alpha + 3 mod{3} = 2alpha^2 + alpha

In GF(2"m"), addition is especially easy, since addition and subtraction modulo 2 are the same thing, 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("p""m") requires up to "m"2 multiplications in GF("p") and up to "m"2 − "m" additions in GF("p").

Some of the methods for reducing these values include:

*Lookup tables — a prestored table of results; mainly used for small fields, otherwise the table is too large to implement
*The Karatsuba-Ofman algorithm — repeatedly breaking the multiplication into pieces, decreasing the total number of multiplications but increasing the number of additions. As seen above, addition is very simple, but the overhead in breaking down and recombining the parts involved in Karatsuba-Ofman make it prohibitive for hardware, although it is often used in software. It can even be used for general multiplication, and is done in many computer algebra systems such as Waterloo Maple.
*Linear feedback shift register-based multiplication
*Subfield computations — breaking the multiplication in GF("p""m") to multiplications in GF("p""x") and GF("p""y"), where "x" × "y" = "m". This is not frequently used for cryptographic purposes, since some composite degree fields are avoided because of known attacks on them.
*Pipelined multipliers — storing intermediate results in buffers so that new values can be loaded into the multiplier faster
*Systolic multipliers — using many cells that communicate with neighboring cells only; typically systolic devices are used for computation-intensive operations where input and output sizes are not as important, such as multiplication.

quaring

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(2"m") much simpler than multiplication [Citation | last1 = Huapeng | first1 = Wu | contribution = On Complexity of Polynomial Basis Squaring in F(2m) | title = Selected Areas in Cryptography: 7th Annual International Workshop, SAC 2000, Waterloo, Ontario, Canada, August 14-15, 2000, | publisher = Springer | pages = 118 | year = 2001 ] .

Inversion

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

*Lookup tables — once again, only for small fields otherwise the table is too large for implementation
*Subfield inversion — by solving systems of equations in subfields
*Repeated square and multiply — for example in GF(2"m"), "A"−1 = "A"2"m" − 2
*The Extended Euclidean algorithm
*The Itoh-Tsujii inversion algorithm

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

ee also

*dual basis
*change of bases


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Polynomial interpolation — In the mathematical subfield of numerical analysis, polynomial interpolation is the interpolation of a given data set by a polynomial. In other words, given some data points (such as obtained by sampling), the aim is to find a polynomial which… …   Wikipedia

  • Polynomial ring — In mathematics, especially in the field of abstract algebra, a polynomial ring is a ring formed from the set of polynomials in one or more variables with coefficients in another ring. Polynomial rings have influenced much of mathematics, from the …   Wikipedia

  • Polynomial long division — In algebra, polynomial long division is an algorithm for dividing a polynomial by another polynomial of the same or lower degree, a generalised version of the familiar arithmetic technique called long division. It can be done easily by hand,… …   Wikipedia

  • polynomial — /pol euh noh mee euhl/, adj. 1. consisting of or characterized by two or more names or terms. n. 2. Algebra. a. (in one variable) an expression consisting of the sum of two or more terms each of which is the product of a constant and a variable… …   Universalium

  • Basis function — In mathematics, particularly numerical analysis, a basis function is an element of the basis for a function space. The term is a degeneration of the term basis vector for a more general vector space; that is, each function in the function space… …   Wikipedia

  • Polynomial — In der Mathematik ist ein Polynom (von griech. πολύ / polý und lat. nomen = „mehrnamig“) eine Summe von Vielfachen von Potenzen mit natürlichzahligen Exponenten einer Variablen, die in den meisten Fällen mit x bezeichnet wird. In der elementaren… …   Deutsch Wikipedia

  • Canonical basis — In mathematics, the notion of canonical basis refers to a basis of an algebraic structure which is canonical in a sense that depends on the precise context:* In a coordinate space, and more generally in a free module, it refers to the standard… …   Wikipedia

  • Primitive polynomial — In field theory, a branch of mathematics, a primitive polynomial is the minimal polynomial of a primitive element of the finite extension field GF( p m ). In other words, a polynomial F(X) with coefficients in GF( p ) = Z/ p Z is a primitive… …   Wikipedia

  • Normal basis — In mathematics, a normal basis in field theory is a special kind of basis for Galois extensions of finite degree, characterised as forming a single orbit for the Galois group. The normal basis theorem states that any finite Galois extension of… …   Wikipedia

  • Dual basis in a field extension — In mathematics, the linear algebra concept of dual basis can be applied in the context of a finite extension L/K, by using the field trace. This requires the property that the field trace TrL/K provides a non degenerate quadratic form over K.… …   Wikipedia