Normal basis

Short description: Mathematical theorem used in cryptography

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 $F\subseteq K$ be a Galois extension with Galois group $G$. The classical normal basis theorem states that there is an element $\beta \in K$ such that $\{\sigma (\beta ):\sigma \in G\}$ forms a basis of $K$, considered as a vector space over $F$. That is, any element $\alpha \in K$ can be written uniquely as $\alpha =\sum _{\sigma \in G}{a}_{\sigma }\sigma (\beta )$ for some coefficients $a_{\sigma }\in F$.

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

Group representation point of view

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; thus K is also a left module for the group algebra F[G]. Every homomorphism of left F[G]-modules $\varphi :F[G]\to K$ is of form $\varphi (\sigma )=\sigma (\beta )$ for some $\beta \in K$. Since $\{\sigma :\sigma \in G\}$ is a linear basis of F[G] over F, we see that $\varphi$ is bijective iff $\beta$ 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 $K\cong F[G]$ as a left $F[G]$-module: K is isomorphic to the regular representation. Also, a given $\beta$ generates a normal basis iff, when considering K as a G-representation, $\beta$ does not lie in any proper subrepresentation.

Case of finite fields

For finite fields this can be stated as follows: Let $F=\mathrm{G}\mathrm{F}(q)={\mathbb{𝔽}}_q$ denote the field of q elements, where q = p^m is a prime power, and let $K=\mathrm{G}\mathrm{F}(q^n)={\mathbb{𝔽}}_{q^n}$ denote its extension field of degree n ≥ 1. Here the Galois group is $G=\text{Gal}(K/F)=\{1,\mathrm{\Phi },{\mathrm{\Phi }}^2,\dots ,{\mathrm{\Phi }}^{n-1}\}$ with ${\mathrm{\Phi }}^n=1,$ a cyclic group generated by the q-power Frobenius automorphism $\mathrm{\Phi }(\alpha )={\alpha }^q,$with ${\mathrm{\Phi }}^n=1={\mathrm{I}\mathrm{d}}_K.$ Then there exists an element β ∈ K such that $$\{\beta ,\mathrm{\Phi }(\beta ),{\mathrm{\Phi }}^2(\beta ),\dots ,{\mathrm{\Phi }}^{n-1}(\beta )\}=\{\beta ,{\beta }^q,{\beta }^{q^2},\dots ,{\beta }^{q^{n-1}}\}$$ is a basis of K over F.

Proof for finite fields

In case the Galois group is cyclic as above, generated by $\mathrm{\Phi }$ with ${\mathrm{\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 $\chi$ from a group $H$ to a field $K$ satisfying $\chi (h_1{h}_2)=\chi (h_1)\chi (h_2)$ and $\chi (1)=1$; then any distinct characters ${\chi }_1,{\chi }_2,\dots$ are linearly independent in the $K$-vector space of mappings $H\to K$. We apply this to the Galois group automorphisms ${\chi }_i={\mathrm{\Phi }}^i:K\to K,$ thought of as mappings from the multiplicative group $H=K^{\times }$. Now $K\cong F^n$as an F-vector space, so we may consider $\mathrm{\Phi }:F^n\to F^n$ as an element of $M_n(F)\subset M_n(K)$; since its powers $1,\mathrm{\Phi },\dots ,{\mathrm{\Phi }}^{n-1}$ are linearly independent over $K$ in $M_n(K)$ and a fortiori over $F$ in $M_n(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 modules over a PID such as

$F[X]$

. Every such module

$M$

of finite dimension over F can be represented as

$M\cong {⨁}_{i=1}^k\frac{F[X]}{(f_i(X))}$

, where

$f_i(X)$

are monic polynomials and

$f_{i+1}(X)$

is a multiple of

$f_i(X)$

, so that the highest

$f_k(X)$

is the monic polynomial of smallest degree annihilating the module. For our cyclic Galois group

$G$

of order n, we have an

$F$

-algebra isomorphism

$F[G]\cong \frac{F[X]}{(X^n-1)}$

taking the generator

$\mathrm{\Phi }$

to the variable

$X$

: this makes every

$F[G]$

-module into an

$F[X]$

-module. Consider

$M=K$

as an

$F[X]$

-module under

$X\alpha =\mathrm{\Phi }(\alpha )$

: the minimal monic polynomial

$f_k(X)$

annihilating

$M$

is the minimal polynomial of

$\mathrm{\Phi }$

, namely

$f_k(X)=X^n-1$

. Since

${\dim }_F(M)=n,$

we can only have

$k=1$

, and

$K\cong \frac{F[X]}{(X^n-1)}$

as

$F[X]$

-modules (but this is not an isomorphism of rings). Thus we have an isomorphism of

$F[G]$

-modules

$K\cong \frac{F[X]}{(X^n-1)}\cong F[G]$

,

under which the basis

$\{1,X,X^2,\dots ,X^{n-1}\}$

corresponds to the basis

$\{1,\mathrm{\Phi },{\mathrm{\Phi }}^2,\dots ,{\mathrm{\Phi }}^{n-1}\}$

of

$F[G]$

on the right side, and to a normal basis

$\{\beta ,\mathrm{\Phi }(\beta ),{\mathrm{\Phi }}^2(\beta ),\dots ,{\mathrm{\Phi }}^{n-1}(\beta )\}$

of

$K$

on the left.

Note that this proof would also apply in characteristic zero for a cyclic Kummer extension.

Example

Consider the field $K=\mathrm{G}\mathrm{F}(2^3)={\mathbb{𝔽}}_8$ over $F=\mathrm{G}\mathrm{F}(2)={\mathbb{𝔽}}_2$, with Frobenius automorphism $\mathrm{\Phi }(\alpha )={\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=X^3-1=(X-1)(X^2+X+1)\in F[X]$$ means we have a direct sum of F[G]-modules (by the Chinese remainder theorem):$$K\cong \frac{F[X]}{(X^3-1)}\cong \frac{F[X]}{(X+1)}\oplus \frac{F[X]}{(X^2+X+1)}.$$ The first component is just $F\subset K$, while the second is isomorphic as an $F[G]$-module to ${\mathbb{𝔽}}_{2^2}\cong {\mathbb{𝔽}}_2[X]/(X^2+X+1)$ under the action $\mathrm{\Phi }\cdot X^i=X^{i+1}.$ (Thus $K\cong {\mathbb{𝔽}}_2\oplus {\mathbb{𝔽}}_4$ as $F[G]$-modules, but not as rings.)

The elements $\beta \in K$ which can be used for a normal basis are precisely those outside either of the submodules, so that $(\mathrm{\Phi }+1)(\beta )\ne 0$ and $({\mathrm{\Phi }}^2+\mathrm{\Phi }+1)(\beta )\ne 0$. In terms of the $G$-orbits of $K$, which correspond to the irreducible factors in: $$t^8-t=t(t+1)(t^3+t+1)(t^3+t^2+1)\in F[t],$$ the elements of the submodule $F={\mathbb{𝔽}}_2$ are the roots of $t(t+1)$; and the nonzero elements of the submodule ${\mathbb{𝔽}}_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=\mathrm{G}\mathrm{F}(2^4)={\mathbb{𝔽}}_{16}$ in which n = 4 is divisible by p = 2, we have the $F[G]$-module isomorphism $$L\cong {\mathbb{𝔽}}_2[X]/(X^4-1)={\mathbb{𝔽}}_2[X]/(X+1{)}^4.$$ Here the operator $\mathrm{\Phi }\cong X$ is not diagonalizable, the module $L$ has nested submodules given by generalized eigenspaces of $\mathrm{\Phi }$, and the normal basis elements β are those outside the largest proper generalized eigenspace, the elements with $(\mathrm{\Phi }+1{)}^3(\beta )\ne 0$.

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 $K=\mathrm{G}\mathrm{F}(2^3)={\mathbb{𝔽}}_8$ above, we may represent elements as bit-strings: $$\alpha =(a_2,a_1,a_0)=a_2{\mathrm{\Phi }}^2(\beta )+a_1\mathrm{\Phi }(\beta )+a_0\beta =a_2{\beta }^4+a_1{\beta }^2+a_0\beta ,$$ where the coefficients are bits $a_i\in \mathrm{G}\mathrm{F}(2)=\{0,1\}.$ Now we can square elements by doing a left circular shift, ${\alpha }^2=\mathrm{\Phi }(a_2,a_1,a_0)=(a_1,a_0,a_2)$, since squaring β⁴ gives β⁸ = β. This makes the normal basis especially attractive for cryptosystems that utilize frequent squaring.

Primitive normal basis

A primitive normal basis of an extension of finite fields $K/F$ is a normal basis that is generated by a primitive element of $K$, that is a generator of the multiplicative group $K^{\times }$. (Note that this is a stronger definition of primitive element than mentioned above: 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.

Proof for the case of infinite fields

Suppose $K/F$ is a finite Galois extension of the infinite field F. Let $n=[K:F]$, $G=\text{Gal}(K/F)=\{{\sigma }_1...{\sigma }_n\}$ with ${\sigma }_1=\text{Id}$. By the primitive element theorem there exists $\alpha \in K$ such that $K=F[\alpha ]$ and ${\sigma }_i(\alpha )\ne {\sigma }_j(\alpha )$ for $i\ne j$; and write ${\alpha }_i={\sigma }_i(\alpha )$. The minimal polynomial f of $\alpha$ over K is:$$f(X)=\prod _{i=1}^n(X-{\alpha }_i),$$a degree n monic polynomial which is irreducible in $K[X]$. Since f is separable (having simple roots) we may define the Lagrange interpolation polynomials $g_1(X),\dots ,g_n(X)$ satisfying $g_i({\alpha }_i)=1$ and $g_i({\alpha }_j)=0$ for $i\ne j$:$$\begin{array}{rl}g(X)& =\frac{f(X)}{(X-\alpha )f^{\prime }(\alpha )}=\prod _{\begin{array}{c}1\le j\le n\\ j\ne i\end{array}}\frac{X-{\alpha }_j}{\alpha -{\alpha }_j},\\ g_i(X)& ={\sigma }_i(g(X))=\frac{f(X)}{(X-{\alpha }_i)f^{\prime }({\alpha }_i)}=\prod _{\begin{array}{c}1\le j\le n\\ j\ne i\end{array}}\frac{X-{\alpha }_j}{{\alpha }_i-{\alpha }_j}.\end{array}$$Next, define an $n\times n$ matrix of polynomials $A=(A_{ij}(X))$ by$$A_{ij}(X)={\sigma }_i({\sigma }_j(g(X))={\sigma }_i(g_j(X)),$$and let $D(X)=\det A(X)$. To see this a non-zero polynomial, observe that $A_{ij}(X)=g_k(X)$, where k is determined by ${\sigma }_k={\sigma }_i\cdot {\sigma }_j$, and $k=1$ iff ${\sigma }_i={\sigma }_j^{-1}$; thus $A(\alpha )$ is the permutation matrix corresponding to the permutation of G which sends each ${\sigma }_i$ to ${\sigma }_i^{-1}$, and $D(\alpha )=\det A(\alpha )=\pm 1$. Since $D(X)$ is a non-zero polynomial, it has only a finite number of roots; and since we assumed F is infinite, we can find $a\in F$ with $D(a)\ne 0$. Define $$\beta =g(a),{\beta }_i=g_i(a)={\sigma }_i(\beta ).$$ We claim that $\{{\beta }_1,\dots ,{\beta }_n\}$ is a normal basis; i.e. that ${\beta }_1,\dots ,{\beta }_n$ are linearly independent over F. Suppose ${\sum }_{j=1}^n{c}_j{\beta }_j=0$ for some $\overrightarrow{c}=(c_1,...,c_n)\in F^n$; applying any ${\sigma }_i$ gives ${\sum }_{j=1}^n{c}_j{\sigma }_i(g_j(a))=0$, so that $A(a)\cdot \overrightarrow{c}=\overrightarrow{0}$. Since $\det A(a)=D(a)\ne 0$, we conclude that $\overrightarrow{c}=\overrightarrow{0}$, which completes the proof.

It is tempting to take $a=\alpha$ because $D(\alpha )\ne 0$, but we need $a\in F$ to conclude that ${\sigma }_i(g_j(a))={\sigma }_i(g_j(X)){|}_{X={\sigma }_i(a)}={\sigma }_i(g_j(X)){|}_{X=a}$ is a matrix entry of $A(a)=A(X){|}_{x=a}$.

Free elements

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.

See also

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

References

• 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. 233. Cambridge University Press. ISBN 978-0-521-56736-7. 
• 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. 
• Menezes, Alfred J., ed (1993). Applications of finite fields. The Kluwer International Series in Engineering and Computer Science. 199. Boston: Kluwer Academic Publishers. ISBN 978-0792392828.