normal basis

Let $F\backslash subset\; K$ be a Galois extension with Galois group $G$. The classical normal basis theorem states that there is an element $\backslash beta\backslash in\; K$ such that $\backslash \{g(\backslash beta)\; :\; g\backslash in\; G\backslash \}$ forms a basis of K, considered as a vector space over F. That is, any element $\backslash alpha\; \backslash in\; K$ can be written uniquely as $\backslash alpha\; =\; \backslash sum\_\{g\backslash in\; G\}\; a\_g\backslash ,\; g(\backslash beta)$ for some elements $a\_g\backslash in\; F.$

A normal basis contrasts with a primitive element basis of the form $\backslash \{1,\backslash beta,\backslash beta^2,\backslash ldots,\backslash beta^\{n-1\}\backslash \}$, where $\backslash beta\backslash in\; K$ is an element whose minimal polynomial has degree $n=[K:F]$.

A field extension {{nowrap|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 $\backslash phi:F[G]\backslash rightarrow\; K$ is of form $\backslash phi(r)\; =\; r\backslash beta$ for some $\backslash beta\; \backslash in\; K$. Since $\backslash \{1\backslash cdot\; \backslash sigma|\; \backslash sigma\; \backslash in\; G\backslash \}$ is a linear basis of F[G] over F, it follows easily that $\backslash phi$ is bijective iff $\backslash beta$ generates a normal basis of K over F. The normal basis theorem therefore amounts to the statement saying that if {{nowrap|K / F}} is finite Galois extension, then $K\; \backslash cong\; F[G]$ as a left $F[G]$-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:{{citation|author1=Nader H. Bshouty|title=Generalizations of the normal basis theorem of finite fields|url=https://hotcrp-vee2014.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1989/CS/CS0578.pdf|page=1|year=1989|author2=Gadiel Seroussi}}; SIAM J. Discrete Math. 3 (1990), no. 3, 330–337. Let $F\; =\; \backslash mathrm\{GF\}(q)=\backslash mathbb\{F\}\_q$ denote the field of q elements, where {{nowrap|1=q = p^m}} is a prime power, and let $K=\; \backslash mathrm\{GF\}(q^n)=\backslash mathbb\{F\}\_\{q^n\}$ denote its extension field of degree {{nowrap|n ≥ 1}}. Here the Galois group is $G\; =\; \backslash text\{Gal\}(K/F)\; =\; \backslash \{1,\backslash Phi,\backslash Phi^2,\backslash ldots,\backslash Phi^\{n-1\}\backslash \}$ with $\backslash Phi^n\; =\; 1,$ a cyclic group generated by the q-power Frobenius automorphism $\backslash Phi(\backslash alpha)=\backslash alpha^q,$with $\backslash Phi^n\; =\; 1\; =\backslash mathrm\{Id\}\_K.$ Then there exists an element {{nowrap|β ∈ K}} such that

$$\backslash \{\backslash beta,\; \backslash Phi(\backslash beta),\; \backslash Phi^2(\backslash beta),\backslash ldots,\backslash Phi^\{n-1\}(\backslash beta)\backslash \}$$

\ = \

\{\beta, \beta^q, \beta^{q^2}, \ldots,\beta^{q^{n-1}}\!\}

is a basis of K over F.

In case the Galois group is cyclic as above, generated by $\backslash Phi$ with $\backslash Phi^n=1,$ 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 $\backslash chi(h\_1h\_2)=\backslash chi(h\_1)\backslash chi(h\_2)$; then any distinct characters $\backslash chi\_1,\backslash chi\_2,\backslash ldots$ are linearly independent in the K-vector space of mappings. We apply this to the Galois group automorphisms $\backslash chi\_i=\backslash Phi^i:\; K\; \backslash to\; K,$ thought of as mappings from the multiplicative group $H=K^\backslash times$. Now $K\backslash cong\; F^n$as an F-vector space, so we may consider $\backslash Phi\; :\; F^n\backslash to\; F^n$ as an element of the matrix algebra M_n(F); since its powers $1,\backslash Phi,\backslash ldots,\backslash Phi^\{n-1\}$ are linearly independent (over K and a fortiori over F), its minimal polynomial must have degree at least n, i.e. it must be $X^n-1$.

The second basic fact is the classification of finitely generated modules over a PID such as $F[X]$. Every such module M can be represented as $M\; \backslash cong\backslash bigoplus\_\{i=1\}^k\; \backslash frac\{F[X]\}\{(f\_i(X))\}$, where $f\_i(X)$ may be chosen so that they are monic polynomials or zero and $f\_\{i+1\}(X)$ is a multiple of $f\_i(X)$. $f\_k(X)$ is the monic polynomial of smallest degree annihilating the module, or zero if no such non-zero polynomial exists. In the first case $\backslash dim\_F\; M\; =\; \backslash sum\_\{i=1\}^k\; \backslash deg\; f\_i$, in the second case $\backslash dim\_F\; M\; =\; \backslash infty$. In our case of cyclic G of size n generated by $\backslash Phi$ we have an F-algebra isomorphism $F[G]\backslash cong\; \backslash frac\; \{F[X]\}\{(X^n-1)\}$ where X corresponds to $1\; \backslash cdot\; \backslash Phi$, so every $F[G]$-module may be viewed as an $F[X]$-module with multiplication by X being multiplication by $1\backslash cdot\backslash Phi$. In case of K this means $X\backslash alpha\; =\; \backslash Phi(\backslash alpha)$, so the monic polynomial of smallest degree annihilating K is the minimal polynomial of $\backslash Phi$. Since K is a finite dimensional F-space, the representation above is possible with $f\_k(X)=X^n-1$. Since $\backslash dim\_F(K)\; =\; n,$ we can only have $k=1$, and $K\; \backslash cong\; \backslash frac\{F[X]\}\{(X^n\{-\}\backslash ,1)\}$ as F[X]-modules. (Note this is an isomorphism of F-linear spaces, but not of rings or F-algebras.) This gives isomorphism of $F[G]$-modules $K\backslash cong\; F[G]$ that we talked about above, and under it the basis $\backslash \{1,X,X^2,\backslash ldots,X^\{n-1\}\backslash \}$ on the right side corresponds to a normal basis $\backslash \{\backslash beta,\; \backslash Phi(\backslash beta),\backslash Phi^2(\backslash beta),\backslash ldots,\backslash Phi^\{n-1\}(\backslash beta)\backslash \}$ of K on the left.

Note that this proof would also apply in the case of a cyclic Kummer extension.

Consider the field $K=\backslash mathrm\{GF\}(2^3)=\backslash mathbb\{F\}\_\{8\}$ over $F=\backslash mathrm\{GF\}(2)=\backslash mathbb\{F\}\_\{2\}$, with Frobenius automorphism $\backslash Phi(\backslash alpha)=\backslash alpha^2$. 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

$$X^n-1\; \backslash \; =\backslash \; X^3-1\backslash \; =\; \backslash \; (X\{-\}1)(X^2\{+\}X\{+\}1)\; \backslash \; \backslash in\backslash \; F[X]$$ means we have a direct sum of F[G]-modules (by the Chinese remainder theorem):$$K\backslash \; \backslash cong\backslash \; \backslash frac\{F[X]\}\{(X^3\{-\}\backslash ,1)\}\; \backslash \; \backslash cong\backslash \; \backslash frac\{F[X]\}\{(X\{+\}1)\}\; \backslash oplus\; \backslash frac\{F[X]\}\{(X^2\{+\}X\{+\}1)\}.$$

The first component is just $F\backslash subset\; K$, while the second is isomorphic as an F[G]-module to $\backslash mathbb\{F\}\_\{2^2\}\; \backslash cong\; \backslash mathbb\{F\}\_2[X]/(X^2\{+\}X\{+\}1)$ under the action $\backslash Phi\backslash cdot\; X^i\; =\; X^\{i+1\}.$ (Thus $K\; \backslash cong\; \backslash mathbb\; F\_2\backslash oplus\; \backslash mathbb\; F\_4$ as F[G]-modules, but not as F-algebras.)

The elements $\backslash beta\backslash in\; K$ which can be used for a normal basis are precisely those outside either of the submodules, so that $(\backslash Phi\{+\}1)(\backslash beta)\backslash neq\; 0$ and $(\backslash Phi^2\{+\}\backslash Phi\{+\}1)(\backslash beta)\backslash neq\; 0$. In terms of the G-orbits of K, which correspond to the irreducible factors of:

$$t^\{2^3\}-t\; \backslash \; =\; \backslash \; t(t\{+\}1)\backslash left(t^3\; +\; t\; +\; 1\backslash right)\backslash left(t^3\; +\; t^2\; +\; 1\backslash right)\backslash \; \backslash in\backslash \; F[t],$$

the elements of $F=\backslash mathbb\{F\}\_2$ are the roots of $t(t\{+\}1)$, the nonzero elements of the submodule $\backslash mathbb\{F\}\_4$ are the roots of $t^3+t+1$, while the normal basis, which in this case is unique, is given by the roots of the remaining factor $t^3\{+\}t^2\{+\}1$.

By contrast, for the extension field $L\; =\; \backslash mathrm\{GF\}(2^4)=\backslash mathbb\{F\}\_\{16\}$ in which {{nowrap|1=n = 4}} is divisible by {{nowrap|1=p = 2}}, we have the F[G]-module isomorphism

$$L\; \backslash \; \backslash cong\backslash \; \backslash mathbb\{F\}\_2[X]/(X^4\{-\}1)\backslash \; =\backslash \; \backslash mathbb\{F\}\_2[X]/(X\{+\}1)^4.$$

Here the operator $\backslash Phi\backslash cong\; X$ is not diagonalizable, the module L has nested submodules given by generalized eigenspaces of $\backslash Phi$, and the normal basis elements β are those outside the largest proper generalized eigenspace, the elements with $(\backslash Phi\{+\}1)^3(\backslash beta)\backslash neq\; 0$.

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 $K=\backslash mathrm\{GF\}(2^3)=\backslash mathbb\{F\}\_\{8\}$ above, we may represent elements as bit-strings:

$$\backslash alpha\; \backslash \; =\backslash \; (a\_2,a\_1,a\_0)\backslash \; =\backslash \; a\_2\backslash Phi^2(\backslash beta)\; +\; a\_1\backslash Phi(\backslash beta)+a\_0\backslash beta\backslash \; =\backslash \; a\_2\backslash beta^4\; +\; a\_1\backslash beta^2\; +a\_0\backslash beta,$$

where the coefficients are bits $a\_i\backslash in\; \backslash mathrm\{GF\}(2)=\backslash \{0,1\backslash \}.$ Now we can square elements by doing a left circular shift, $\backslash alpha^2=\backslash Phi(a\_2,a\_1,a\_0)\; =\; (a\_1,a\_0,a\_2)$, since squaring β⁴ gives {{nowrap|1=β⁸ = β}}. This makes the normal basis especially attractive for cryptosystems that utilize frequent squaring.

Suppose $K/F$ is a finite Galois extension of the infinite field F. Let {{nowrap|1=[K : F] = n}}, $\backslash text\{Gal\}(K/F)\; =\; G\; =\backslash \{\backslash sigma\_1...\backslash sigma\_n\backslash \}$, where $\backslash sigma\_1\; =\; \backslash text\{Id\}$. By the primitive element theorem there exists $\backslash alpha\; \backslash in\; K$ such $i\backslash ne\; j\backslash implies\; \backslash sigma\_i(\backslash alpha)\backslash ne\backslash sigma\_j(\backslash alpha)$ and $K=F[\backslash alpha]$. Let us write $\backslash alpha\_i\; =\; \backslash sigma\_i(\backslash alpha)$. $\backslash alpha$'s (monic) minimal polynomial f over K is the irreducible degree n polynomial given by the formula

$$\backslash begin\; \{align\}$$

f(X) &= \prod_{i=1}^n(X - \alpha_i)

\end {align}

Since f is separable (it has simple roots) we may define

\begin {align}

g(X) &= \ \frac{f(X)}{(X-\alpha)f'(\alpha)}\\

g_i(X) &= \ \frac{f(X)}{(X-\alpha_i) f'(\alpha_i)} =\ \sigma_i(g(X)).

\end {align}

In other words,

$$\backslash begin\; \{align\}$$

g_i(X)&= \prod_{\begin {array}{c}1 \le j \le n \\ j\ne i\end {array}}\frac{X-\alpha_j}{\alpha_i - \alpha_j}\\

g(X)&= g_1(X).

\end {align}

Note that $g(\backslash alpha)=1$ and $g\_i(\backslash alpha)=0$ for $i\; \backslash ne\; 1$. Next, define an $n\; \backslash times\; n$ matrix A of polynomials over K and a polynomial D by

\begin {align}

A_{ij}(X) &= \sigma_i(\sigma_j(g(X)) = \sigma_i(g_j(X))\\

D(X) &= \det A(X).

\end {align}

Observe that $A\_\{ij\}(X)\; =\; g\_k(X)$, where k is determined by $\backslash sigma\_k\; =\; \backslash sigma\_i\; \backslash cdot\; \backslash sigma\_j$; in particular $k=1$ iff $\backslash sigma\_i\; =\; \backslash sigma\_j^\{-1\}$. It follows that $A(\backslash alpha)$ is the permutation matrix corresponding to the permutation of G which sends each $\backslash sigma\_i$ to $\backslash sigma\_i^\{-1\}$. (We denote by $A(\backslash alpha)$ the matrix obtained by evaluating $A(X)$ at $x=\backslash alpha$.) Therefore, $D(\backslash alpha)\; =\; \backslash det\; A(\backslash alpha)\; =\; \backslash pm\; 1$. 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 $a\backslash in\; F$ such that $D(a)\backslash ne\; 0$. Define

\begin {align}

\beta &= g(a) \\

\beta_i &= g_i(a) = \sigma_i(\beta).

\end {align}

We claim that $\backslash \{\backslash beta\_1,\; \backslash ldots,\; \backslash beta\_n\backslash \}$ is a normal basis. We only have to show that $\backslash beta\_1,\; \backslash ldots,\backslash beta\_n$ are linearly independent over F, so suppose $\backslash sum\_\{j=1\}^n\; x\_j\; \backslash beta\_j\; =\; 0$ for some $x\_1...x\_n\backslash in\; F$. Applying the automorphism $\backslash sigma\_i$ yields $\backslash sum\_\{j=1\}^n\; x\_j\; \backslash sigma\_i(g\_j(a))\; =\; 0$ for all i. In other words, $A(a)\; \backslash cdot\; \backslash overline\; \{x\}\; =\; \backslash overline\; \{0\}$. Since $\backslash det\; A(a)\; =\; D(a)\; \backslash ne\; 0$, we conclude that $\backslash overline\; x\; =\; \backslash overline\; 0$, which completes the proof.

It is tempting to take $a=\backslash alpha$ because $D(\backslash alpha)\backslash neq0$. But this is impermissible because we used the fact that $a\; \backslash in\; F$ to conclude that for any F-automorphism $\backslash sigma$ and polynomial $h(X)$ over $K$ the value of the polynomial $\backslash sigma(h(X))$ at a equals $\backslash sigma(h(a))$.

A primitive normal basis of an extension of finite fields {{nowrap|E / F}} is a normal basis for {{nowrap|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 extension of finite fields possesses a primitive normal basis, the case when F is a prime field having been settled by Harold Davenport.

If {{nowrap|K / F}} is a Galois extension and x in K generates a normal basis over F, then x is free in {{nowrap|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 {{nowrap|K / K^H}}, then x is said to be completely free in {{nowrap|K / F}}. Every Galois extension has a completely free element.Dirk Hachenberger, Completely free elements, in Cohen & Niederreiter (1996) pp. 97–107 {{zbl|0864.11066}}

• Dual basis in a field extension
• Polynomial basis
• Zech's logarithm

{{Reflist}}

• {{cite book | editor1-first=S. | editor1-last=Cohen | editor2-first=H. | editor2-last=Niederreiter|editor2-link = Harald Niederreiter | title=Finite Fields and Applications. Proceedings of the 3rd international conference, Glasgow, UK, July 11–14, 1995 | publisher=Cambridge University Press | isbn=978-0-521-56736-7 | year=1996 | series=London Mathematical Society Lecture Note Series | volume=233 | zbl=0851.00052 }}
• {{cite journal | last1=Lenstra | first1=H.W. Jr | author1-link=Hendrik Lenstra | last2=Schoof | first2=R.J. | author2-link=René Schoof | title=Primitive normal bases for finite fields | zbl=0615.12023 | journal=Mathematics of Computation | volume=48 | issue=177 | pages=217–231 | year=1987 | jstor=2007886 | doi=10.2307/2007886| doi-access=free | hdl=1887/3824 | hdl-access=free }}
• {{cite book | editor1-last=Menezes | editor1-first=Alfred J. | editor1-link=Alfred Menezes | title=Applications of finite fields | zbl=0779.11059 | series=The Kluwer International Series in Engineering and Computer Science | volume=199 | location=Boston | publisher= Kluwer Academic Publishers | year=1993 | isbn=978-0792392828 }}

{{Authority control}}

Category:Linear algebra

Category:Field (mathematics)

Category:Abstract algebra

Category:Cryptography