Normal basis

In mathematics, a normal 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 applying the Frobenius p-th power mapping repeatedly, where p is the characteristic of the field. Let GF(p^m) be a field with p^m elements, and β an element of it such that the m elements

$\{ \beta, \beta^p, \beta^{p^2}, \ldots, \beta^{p^{m-1}} \}$

are linearly independent. Then this set forms a normal basis for GF(p^m) over GF(p).

Usage

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

When representing elements as a binary string (e.g. in GF(2³) the most significant bit represents β²²=β⁴, the middle bit represents β²¹=β², and the least significant bit represents β²⁰=β), we can square elements by doing a left circular shift (left shifting β⁴ would give β⁸, but since we are working in GF(2³) this wraps around to β). 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 E/F is a normal basis for E/F which 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.

Free elements

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.^[1]

See also

• Dual basis in a field extension
• Polynomial basis
• Zech's logarithms for reducing high-order polynomials to those within the field

References

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. 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.
• Stewart, Ian (1990). Galois theory (3rd ed.). CRC Press. ISBN 978-0-412-34550-0. Zbl 1049.12001.