Jump to content

Normal basis

From Wikipedia, the free encyclopedia

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 some elements

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

Group representation point of view[edit]

A field extension K / F with Galois group G can be naturally viewed as a representation of the group G over the field F in which each automorphism is represented by itself. Representations of G over the field F can be viewed as left modules for the group algebra F[G]. Every homomorphism of left F[G]-modules is of form for some . Since is a linear basis of F[G] over F, it follows easily that is bijective iff generates a normal basis of K over F. The normal basis theorem therefore amounts to the statement saying that if K / F is finite Galois extension, then as left -module. In terms of representations of G over F, this means that K is isomorphic to the regular representation.

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 q-power 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 Mn(F); since its powers are linearly independent (over K and a fortiori over F), its minimal polynomial must have degree at least n, i.e. it must be .

The second basic fact is the classification of finitely generated modules over a PID such as . Every such module M can be represented as , where may be chosen so that they are monic polynomials or zero and is a multiple of . is the monic polynomial of smallest degree annihilating the module, or zero if no such non-zero polynomial exists. In the first case , in the second case . In our case of cyclic G of size n generated by we have an F-algebra isomorphism where X corresponds to , so every -module may be viewed as an -module with multiplication by X being multiplication by . In case of K this means , so the monic polynomial of smallest degree annihilating K is the minimal polynomial of . Since K is a finite dimensional F-space, the representation above is possible with . Since we can only have , and as F[X]-modules. (Note this is an isomorphism of F-linear spaces, but not of rings or F-algebras.) This gives isomorphism of -modules that we talked about above, and under it the basis on the right side 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.

Proof for the case of infinite fields[edit]

Suppose is a finite Galois extension of the infinite field F. Let [K : F] = n, , where . By the primitive element theorem there exists such and . Let us write . 's (monic) minimal polynomial f over K is the irreducible degree n polynomial given by the formula

Since f is separable (it has simple roots) we may define
In other words,
Note that and for . Next, define an matrix A of polynomials over K and a polynomial D by
Observe that , where k is determined by ; in particular iff . It follows that is the permutation matrix corresponding to the permutation of G which sends each to . (We denote by the matrix obtained by evaluating at .) Therefore, . We see that D is a non-zero polynomial, and therefore it has only a finite number of roots. Since we assumed F is infinite, we can find such that . Define
We claim that is a normal basis. We only have to show that are linearly independent over F, so suppose for some . Applying the automorphism yields for all i. In other words, . Since , we conclude that , which completes the proof.

It is tempting to take because . But this is impermissible because we used the fact that to conclude that for any F-automorphism and polynomial over the value of the polynomial at a equals .

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 K×. (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 K 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