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 = p" 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 "β" gives "β" = "β". This makes the normal basis especially attractive for cryptosystems that utilize frequent squaring. Proof for the case of infinite fields. Suppose formula_11 is a finite Galois extension of the infinite field "F". Let formula_95, formula_96, where formula_97. By the primitive element theorem there exists formula_5 such that formula_99. Let "f" be the minimal monic polynomial of formula_100. Then "f" is an irreducible monic polynomial of degree "n" over "F". Let formula_101. Since "f" is of degree "n", we  have formula_102 for formula_103. Let formula_104 In other words, formula_105 Note that formula_106 and formula_107 for formula_108. Next, define an formula_109 matrix "A" of polynomials over "K" and a 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 the permutation matrix corresponding to the permutation of "G" which sends each formula_116 to formula_117. (We denote by formula_115 the matrix obtained by evaluating formula_119 at formula_120.) Therefore, formula_121. 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 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 the automorphism formula_116 yields formula_130 for all "i". In other words, formula_131. Since formula_132, we conclude that formula_133, which completes the proof. It is tempting to take formula_134 because formula_135. But this is impermissible because we used the fact that formula_136 to conclude that for any "F"-automorphism formula_137 and polynomial formula_138 over formula_139 the value of the polynomial  formula_140 at formula_141 equals formula_142. 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_143. (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", "x" is free for "K"/"K", then "x" is said to be completely free in "K"/"F". Every Galois extension has a completely free element.