Normal basis

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.
Let formula_1 be a Galois extension with Galois group formula_2. The classical normal basis theorem states that there is an element formula_3 such that formula_4 forms a basis of "K", considered as a vector space over "F". That is, any element formula_5 can be written uniquely as formula_6 for some elements formula_7
A normal basis contrasts with a primitive element basis of the form formula_8, where formula_3 is an element whose minimal polynomial has degree formula_10.
Group representation point of view.
A field extension formula_11 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 formula_12. Every homomorphism of left formula_12-modules formula_14 is of form formula_15 for some formula_16. Since formula_17 is a linear basis of formula_12 over "F", it follows easily that formula_19 is bijective iff formula_20 generates a normal basis of "K" over "F". The normal basis theorem therefore amounts to the statement saying that if formula_11 is finite Galois extension, then formula_22 as left formula_12-module. In terms of representations of "G" over "F", this means that "K" is isomorphic to the regular representation.
Case of finite fields.
For finite fields this can be stated as follows: Let formula_24 denote the field of "q" elements, where "q = pm" is a prime power, and let formula_25 denote its extension field of degree "n" ≥ 1. Here the Galois group is formula_26 with formula_27 a cyclic group generated by the "q"-power Frobenius automorphism formula_28with formula_29 Then there exists an element such that
formula_30
is a basis of "K" over "F".
Proof for finite fields.
In case the Galois group is cyclic as above, generated by formula_31 with formula_32 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 formula_33; then any distinct characters formula_34 are linearly independent in the "K"-vector space of mappings. We apply this to the Galois group automorphisms formula_35 thought of as mappings from the multiplicative group formula_36. Now formula_37as an "F"-vector space, so we may consider formula_38 as an element of the matrix algebra formula_39 since its powers formula_40 are linearly independent (over "K" and a fortiori over "F"), its minimal polynomial must have degree at least "n", i.e. it must be formula_41.
The second basic fact is the classification of finitely generated modules over a PID such as formula_42. Every such module "M" can be represented as formula_43, where formula_44 may be chosen so that they are monic polynomials or zero and formula_45 is a multiple of formula_44. formula_47 is the monic polynomial of smallest degree annihilating the module, or zero if no such non-zero polynomial exists. In the first case formula_48, in the second case formula_49. In our case of cyclic "G" of size "n" generated by formula_31 we have an "F"-algebra isomorphism formula_51 where "X" corresponds to formula_52, so every formula_12-module may be viewed as an formula_42-module with multiplication by "X" being multiplication by formula_55. In case of "K" this means formula_56, so the monic polynomial of smallest degree annihilating "K" is the minimal polynomial of formula_31. Since "K" is a finite dimensional "F"-space, the representation above is possible with formula_58. Since formula_59 we can only have formula_60, and formula_61 as formula_42-modules. (Note this is an isomorphism of "F"-linear spaces, but "not" of rings or "F"-algebras!) This gives isomorphism of formula_12-modules formula_64 that we talked about above, and under it the basis formula_65 on the right side corresponds to a normal basis formula_66 of "K" on the left.
Note that this proof would also apply in the case of a cyclic Kummer extension.
Example.
Consider the field formula_67 over formula_68, with Frobenius automorphism formula_69. 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 
formula_70 means we have a direct sum of "F"["G"]-modules (by the Chinese remainder theorem):formula_71
The first component is just formula_1, while the second is isomorphic as an "F"["G"]-module to formula_73 under the action formula_74 (Thus formula_75 as "F"["G"]-modules, but "not" as "F"-algebras.)
The elements formula_3 which can be used for a normal basis are precisely those outside either of the submodules, so that formula_77 and formula_78. In terms of the "G"-orbits of "K", which correspond to the irreducible factors of:
formula_79
the elements of formula_80 are the roots of formula_81, the nonzero elements of the submodule formula_82 are the roots of formula_83, while the normal basis, which in this case is unique, is given by the roots of the remaining factor formula_84.
By contrast, for the extension field formula_85 in which "n" = 4 is divisible by "p" = 2, we have the "F"["G"]-module isomorphism 
formula_86
Here the operator formula_87 is not diagonalizable, the module "L" has nested submodules given by generalized eigenspaces of formula_31, and the normal basis elements "β" are those outside the largest proper generalized eigenspace, the elements with formula_89.
Application to cryptography.
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 formula_67 above, we may represent elements as bit-strings:
formula_91
where the coefficients are bits formula_92 Now we can square elements by doing a left circular shift, formula_93, 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.
Suppose formula_11 is finite Galois extension of infinite field "F". Let formula_95, formula_96, where formula_97. By primitive element theorem there exist formula_5 such that formula_99. Let "f" be the minimal monic polynomial of formula_100. Then "f" is irreducible monic polynomial of degree "n" over "F"/ Denote formula_101. Since "f" is of degree "n", we have formula_102 for formula_103. Denote 
formula_104
In other words, we have
formula_105
Note that formula_106 and formula_107 for formula_108. Next, define formula_109 matrix "A" of polynomials over "K" and polynomial "D" by
formula_110
Observe that formula_111, where "k" is determined by formula_112, in particular formula_60 iff formula_114. It follows that formula_115 is permutation matrix corresponding to the permutation of "G" which sends each formula_116 to formula_117. (We denote by formula_115 matrix elements of which are values of elements of formula_119 at formula_100.)Therefore, we have formula_121. We see that "D" is a non-zero polynomial, therefore it may have only finite number of roots. Since we assume "F" is infinite, we can find formula_122 such that formula_123. Define
formula_124
We claim that formula_125 is a normal basis. We only have to show that formula_126 are linearly independent over "F", so suppose formula_127 for some formula_128. Applying automorphism formula_116 we get formula_130 for all "i". In other words, formula_131. Since formula_132,we conclude formula_133, which completes the proof.
Note that we have made use of the fact that formula_134, so for any "F"-automorphism formula_135 and polynomial formula_136 over formula_137 value of the polynomial formula_138 at formula_139 equals formula_140. Therefore, we could not have simply taken formula_141.
Primitive normal basis.
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 formula_142. (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.
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 "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.