Binary Fields

A field is a set equipped with addition and multiplication operations, which satisfy the commutative, associative and distributive laws, and where everything nonzero has an inverse. A finite field is moreover finite.

The finite fields you're probably most used to look like $\mathbb{F}_p = \{0, \ldots , p - 1\}$, where $p$ is a large prime. Arithmetic in that set is carried out modulo $p$. Elements of the field can be represented, concretely, as $\lceil \log_2 p \rceil$-bit strings. Some of those strings—i.e., the ones representing integers in the high range $\{p, \ldots , \lceil \log_2 p \rceil - 1\}$—will be "off-limits".

Here, we work in characteristic 2. This means that we construct our fields differently.

Construction

The simplest binary field is $\mathbb{F}_2 = \{0, 1\}$, the field with two elements.

By taking algebraic extensions of this field, we can get further binary fields. We pick a bit-length. For now, we'll stick with $128$. We fix once and for all a global irreducible polynomial $f(X) \in \mathbb{F}_2[X]$ of degree $128$. The corresponding quotient ring $\mathbb{F}_2[X] / (f(X))$ is a field, namely $\mathbb{F}_{2^{128}}$.

Concretely, we can represent elements $\alpha \in \mathbb{F}_{2^{128}}$ as polynomials of degree less than $128$; say, $\alpha = \sum_{i = 0}^{127} \alpha_i \cdot X^i$. In other words, the list of monomials $1, X, \ldots , X^{127}$ is an $\mathbb{F}_2$-basis of $\mathbb{F}_{2^{128}}$. Thus elements of $\mathbb{F}_{2^{128}}$ get represented in practice as $128$-bit words (or say as pairs of 64-bit words).

Algebraic Properties

We fix a binary field, say $\mathbb{F}_{2^{128}}$. The multiplicative group of units of $\mathbb{F}_{2^{128}}$, written $\mathbb{F}_{2^{128}}^*$, is the set of nonzero elements of $\mathbb{F}_{2^{128}}$, with multiplication as its group operation. The multiplicative group of units of a finite field is cyclic, and so $\mathbb{F}_{2^{128}}^*$ in particular is. This means that we can fix an element $g \in \mathbb{F}_{2^{128}}^*$ such that the powers $g^a$, for $a \in \{0, \ldots , 2^{128} - 2\}$, exactly exhaust $\mathbb{F}_{2^{128}}^*$.

In $\mathbb{F}_{2^{128}}$, the Frobenius endomorphism $\varphi$ sends $\varphi : \alpha \mapsto \alpha^2$. The Frobenius endomorphism is $\mathbb{F}_2$-linear and injective; in finite fields, it's also surjective, and so invertible.