KNOWPIA
WELCOME TO KNOWPIA

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.

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 .

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.

For finite fields this can be stated as follows:^{[1]} Let denote the field of *q* elements, where *q* = *p*^{m} 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*.

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 M_{n}(*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.

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 .

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.

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 .

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.

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 *K*^{H}, *x* is free for *K* / *K*^{H}, then *x* is said to be **completely free** in *K* / *F*. Every Galois extension has a completely free element.^{[2]}

- Cohen, S.; Niederreiter, H., eds. (1996).
*Finite Fields and Applications. Proceedings of the 3rd international conference, Glasgow, UK, July 11–14, 1995*. London Mathematical Society Lecture Note Series. Vol. 233. Cambridge University Press. ISBN 978-0-521-56736-7. Zbl 0851.00052. - Lenstra, H.W. Jr; Schoof, R.J. (1987). "Primitive normal bases for finite fields".
*Mathematics of Computation*.**48**(177): 217–231. doi:10.2307/2007886. hdl:1887/3824. JSTOR 2007886. Zbl 0615.12023. - Menezes, Alfred J., ed. (1993).
*Applications of finite fields*. The Kluwer International Series in Engineering and Computer Science. Vol. 199. Boston: Kluwer Academic Publishers. ISBN 978-0792392828. Zbl 0779.11059.