In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, a normal basis in field theory

Field theory (mathematics)

Field theory is a branch of mathematics which studies the properties of fields. A field is a mathematical entity for which addition, subtraction, multiplication and division are well-defined....

 is a special kind of basis

Basis (linear algebra)

In linear algebra, a basis is a set of linearly independent vectors that, in a linear combination, can represent every vector in a given vector space or free module, or, more simply put, which define a "coordinate system"...

 for Galois extension

Galois extension

In mathematics, a Galois extension is an algebraic field extension E/F satisfying certain conditions ; one also says that the extension is Galois. The significance of being a Galois extension is that the extension has a Galois group and obeys the fundamental theorem of Galois theory.The definition...

s of finite degree, characterised as forming a single orbit for the Galois group

Galois group

In mathematics, more specifically in the area of modern algebra known as Galois theory, the Galois group of a certain type of field extension is a specific group associated with the field extension...

. The normal basis theorem states that any finite Galois extension of fields has a normal basis. In algebraic number theory

Algebraic number theory

Algebraic number theory is a major branch of number theory which studies algebraic structures related to algebraic integers. This is generally accomplished by considering a ring of algebraic integers O in an algebraic number field K/Q, and studying their algebraic properties such as factorization,...

 the study of the more refined question of the existence of a normal integral basis is part of Galois module

Galois module

In mathematics, a Galois module is a G-module where G is the Galois group of some extension of fields. The term Galois representation is frequently used when the G-module is a vector space over a field or a free module over a ring, but can also be used as a synonym for G-module...

 theory.

In the case of finite field

Finite field

In abstract algebra, a finite field or Galois field is a field that contains a finite number of elements. Finite fields are important in number theory, algebraic geometry, Galois theory, cryptography, and coding theory...

s, this means that each of the basis elements is related to any one of them by applying the p-th power mapping repeatedly, where p is the characteristic

Characteristic (algebra)

In mathematics, the characteristic of a ring R, often denoted char, is defined to be the smallest number of times one must use the ring's multiplicative identity element in a sum to get the additive identity element ; the ring is said to have characteristic zero if this repeated sum never reaches...

 of the field. Let GF(p^m) be a field with p^m elements, and β an element of it such that the m elements


are linearly independent. Then this set forms a normal basis for GF(p^m).

Usage

This basis is frequently used in cryptographic

Cryptography

Cryptography is the practice and study of techniques for secure communication in the presence of third parties...

 applications that are based on the discrete logarithm problem such as elliptic curve cryptography

Elliptic curve cryptography

Elliptic curve cryptography is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor S...

. Hardware implementations of normal basis arithmetic typically have far less power consumption than other bases.

When representing elements as a binary string (e.g. in GF(2³) the most significant bit represents β⁴, the least significant bit represents β), we can square elements by doing a left circular shift with wraparound (left shifting β⁴ would give β⁸, but since we are working in GF(2³) this wraps around to β). This makes the normal basis especially attractive for cryptosystems that utilize frequent squaring.

See also

• Change of bases
• Dual basis in a field extension
  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...
  
  
• Polynomial basis
  Polynomial basis
  In mathematics, the polynomial basis is a basis for finite extensions of finite fields.Let α ∈ GF be the root of a primitive polynomial of degree m over GF...
  
  
• Zech's logarithms
  Zech's logarithms
  Zech's logarithms are used with finite fields to reduce a high-degree polynomial that is not in the field to an element in the field...
  
  for reducing high-order polynomials to those within the field