Normal basis

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

In mathematics, specifically the algebraic theory of fields, a normal basis 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 fields has a normal basis. In algebraic number theory, the study of the more refined question of the existence of a normal integral basis is part of Galois module theory.

Normal basis theorem[edit]

Let be a Galois extension with Galois group . The classical normal basis theorem states that there is an element such that forms a basis of K, considered as a vector space over F. That is, any element can be written uniquely as for coefficients

A normal basis contrasts with a primitive element basis of the form , where is an element whose minimal polynomial has degree .

Case of finite fields[edit]

For finite fields this can be stated as follows:[1] Let denote the field of q elements, where q = pm is a prime power, and let denote its extension field of degree n ≥ 1. Here the Galois group is with a cyclic group generated by the relative Frobenius automorphism with Then there exists an element βK such that

is a basis of K over F.

Proof for finite fields[edit]

In case the Galois group is cyclic as above, generated by with the Normal Basis Theorem follows from two basic facts. The first is the linear independence of characters: a multiplicative character is a mapping χ from a group H to a field K satisfying ; then any distinct characters are linearly independent in the K-vector space of mappings. We apply this to the Galois group automorphisms thought of as mappings from the multiplicative group . Now as an F-vector space, so we may consider as an element of the matrix algebra since its powers are linearly independent (over K and a fortiori over F), its minimal polynomial[disambiguation needed] must have degree at least n, i.e. it must be . We conclude that the group algebra of G is a quotient of the polynomial ring F[X], and the F-vector space K is a module (or representation) for this algebra.

The second basic fact is the classification of modules over a PID such as F[G]. These are just direct sums of cyclic modules of the form where f(x) must be divisible by Xn 1. (Here G acts by ) But since we can only have f(x) = Xn 1, and

as F[G]-modules, namely the regular representation of G. (Note this is not an isomorphism of rings or F-algebras!) Now the basis on the right side of this isomorphism corresponds to a normal basis of K on the left.

Note that this proof would also apply in the case of a cyclic Kummer extension.

Example[edit]

Consider the field over , with Frobenius automorphism . The proof above clarifies the choice of normal bases in terms of the structure of K as a representation of G (or F[G]-module). The irreducible factorization

means we have a direct sum of F[G]-modules (by the Chinese remainder theorem):

The first component is just , while the second is isomorphic as an F[G]-module to under the action (Thus as F[G]-modules, but not as F-algebras.)

The elements which can be used for a normal basis are precisely those outside either of the submodules, so that and . In terms of the G-orbits of K, which correspond to the irreducible factors of:

the elements of are the roots of , the nonzero elements of the submodule are the roots of , while the normal basis, which in this case is unique, is given by the roots of the remaining factor .

By contrast, for the extension field in which n = 4 is divisible by p = 2, we have the F[G]-module isomorphism

Here the operator is not diagonalizable, the module L has nested submodules given by generalized eigenspaces of , and the normal basis elements β are those outside the largest proper generalized eigenspace, the elements with .

Application to cryptography[edit]

The normal basis is frequently used in cryptographic applications based on the discrete logarithm problem, such as elliptic curve cryptography, since arithmetic using a normal basis is typically more computationally efficient than using other bases.

For example, in the field above, we may represent elements as bit-strings:

where the coefficients are bits Now we can square elements by doing a left circular shift, , since squaring β4 gives β8 = β. This makes the normal basis especially attractive for cryptosystems that utilize frequent squaring.

Primitive normal basis[edit]

A primitive normal basis of an extension of finite fields E/F is a normal basis for E/F that is generated by a primitive element of E, that is a generator of the multiplicative group (Note that this is a more restrictive definition of primitive element than that mentioned above after the general Normal Basis Theorem: one requires powers of the element to produce every non-zero element of K, not merely a basis.) Lenstra and Schoof (1987) proved that every finite field extension possesses a primitive normal basis, the case when F is a prime field having been settled by Harold Davenport.

Free elements[edit]

If K/F is a Galois extension and x in E generates a normal basis over F, then x is free in K/F. If x has the property that for every subgroup H of the Galois group G, with fixed field KH, x is free for K/KH, then x is said to be completely free in K/F. Every Galois extension has a completely free element.[2]

See also[edit]

References[edit]

  1. ^ Nader H. Bshouty; Gadiel Seroussi (1989), Generalizations of the normal basis theorem of finite fields (PDF), p. 1; SIAM J. Discrete Math. 3 (1990), no. 3, 330–337.
  2. ^ Dirk Hachenberger, Completely free elements, in Cohen & Niederreiter (1996) pp.97-107 Zbl 0864.11066