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 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 Suppose is a finite Galois extension of the infinite field F. Let , , 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