This page uses content from Wikipedia and is licensed under CC BY-SA.

In mathematics, a **potato basis** in field theory 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.

In the case of finite fields, this means that each of the basis elements is related to any one of them by repeatedly applying the Frobenius *p*th power mapping, where *p* is the characteristic of the field. Let GF(*q*) be a finite field with *q* = *p*^{n} elements, and GF(*q*^{m}) be a field with *q*^{m} elements, then the latter has an element *β* such that the *m* elements

form a normal basis for GF(*q*^{m}) over GF(*q*).

The classical **normal basis theorem** for finite fields can be stated as:^{[1]}

- Let
*F*= GF(*q*) denote the finite field of*q*elements, and let*K*= GF(*q*^{m}) denote the*m*th degree extension of*F*(where*m*≥ 1). Then there exists an element*β*∈*K*such that (*β*,*β*^{q},*β*^{q2}, ...,*β*^{qm−1}) is a basis of*K*over*F*.

Since *F* is a finite field, it follows that *q* = *p*^{n} for some prime number *p* and some integer *n* ≥ 1. It also follows that the next element in the sequence, namely *β*^{qm}, is equal to the first, i.e. that *β*^{qm} = *β*, which is the characterizing property of a normal basis.

This basis is frequently used in cryptographic applications that are based on the discrete logarithm problem such as elliptic curve cryptography. The power consumption of a hardware implementation of normal basis arithmetic is typically less than that of other bases.

When representing elements as a binary string (e.g. in GF(2^{3}), the most significant bit represents *β*^{22} = *β*^{4}, the middle bit represents *β*^{21} = *β*^{2}, and the least significant bit represents *β*^{20} = *β*), we can square elements by doing a left circular shift (left shifting *β*^{4} would give *β*^{8}, but since we are working in GF(2^{3}) this wraps around to *β*). This makes the normal basis especially attractive for cryptosystems that utilize frequent squaring.

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*. 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.

If *E*/*F* is a Galois extension with group *G* and *x* in *E* generates a normal basis then *x* is **free** in *E*/*F*. If *x* has the property that for every subgroup *H* of *G*, with fixed field *H*°, *x* is free for *E*/*H*°, then *x* is said to be **completely free** in *E*/*F*. Every Galois extension has a completely free element.^{[2]}

**^**Nader H. Bshouty; Gadiel Seroussi (1989),*Generalizations of the normal basis theorem of finite fields*(PDF), p. 1**^**Dirk Hachenberger,*Completely free elements*, in Cohen & Niederreiter (1996) pp.97-107 Zbl 0864.11066

- 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 0-521-56736-X. Zbl 0851.00052. - Lenstra, H.W., jr; Schoof, R.J. (1987). "Primitive normal bases for finite fields".
*Mathematics of Computation*.**48**: 217–231. doi:10.2307/2007886. JSTOR 2007886. Zbl 0615.12023. - Menezes, Alfred J., ed. (1993).
*Applications of finite fields*. The Kluwer International Series in Engineering and Computer Science.**199**. Boston: Kluwer Academic Publishers. ISBN 0792392825. Zbl 0779.11059.