Appendix

A Crash Course in Binary Finite Fields

Prime numbers are important in cryptography mainly because of the special structure they impart to modular arithmetic. For any number $\nmod$ , we can define sensible addition, subtraction, and multiplication operations over the elements of $\Z_\nmod$ . But only when $\nmod$ is prime can we also define “division” (section 3.4). In the study of abstract algebra, a set of items/objects that support addition, subtraction, multiplication, and division in the usual ways is called a field. Thus, $\Z_\nmod$ is a field when $\nmod$ is prime.

Computers (and computer scientists) love powers of two, so in this chapter we will see how to construct a field with $2^k$ elements. The elements of this field are strings from $\bits^k$ , and we will interpret each string as the encoding of a polynomial with 0/1 coefficients, and degree less than $k$ .

Example .1 (Binary field element)

$\bit{11001}$ represents the polynomial $\bit{1} X^4 + \bit{1} X^3 + \bit{0} X^2 + \bit{0} X + \bit{1} = X^4 + X^3 + 1$ .

Arithmetic Modulo a Polynomial: Reducing a number $A$ modulo another number $\nmod$ means: Divide $A$ by $\nmod$ and take the remainder. We can similarly reduce polynomials modulo another polynomial, by dividing and taking the remainder. But no one likes polynomial long division, so here's another way to think about modular reductions.

Arithmetic mod $\nmod$ means following the logical consequences of deciding that $\nmod = 0$ . For example, when working mod 11, we boldly decide that 11 = 0. Hence, you can reduce 42 mod 11 as:

42 = 11 + 11 + 11 + 9 ~~\text{``=''}~~ 0 + 0 + 0 + 9 = 9.

We can think the same way about reduction modulo a polynomial. If we are working mod $X^5 + X^2 + 1$ , then we can boldly decide that $X^5 + X^2 + 1 = 0$ and see what happens. But it is more convenient to rearrange this equation as:

X^5 = -X^2 - 1.

Now you can reduce $X^7 + X^4 + X$ mod $X^5 + X^2 +1$ via:

\begin{aligned} X^7 + X^4 + X &= X^2 \cdot \hl{X^5} + X^4 + X \\ &= X^2 \bigl( \hl{-X^2 - 1} \bigr) + X^4 + X \\ &= -X^4 - X^2 + X^4 + X \\ &= -X^2 + X.\end{aligned}

Try the same calculation with polynomial long division and see whether you get the same answer.

Irreducible polynomials: A polynomial is irreducible if it cannot be factored as the product of lower-degree polynomials. Just as a prime modulus is special for integer arithmetic, an irreducible polynomial is special for polynomial arithmetic.

Definition .2 (Binary finite field)

Let $P(X)$ be an irreducible polynomial of degree $k$ . Then the binary finite field $GF(2^k)$ consists of the elements of $\bits^k$ . We interpret each element as the coefficients of polynomials of degree less than $k$ , and equip the elements with the following operations:

addition: add the polynomials, reducing coefficients mod 2.
multiplication: multiply the polynomials, reducing coefficients mod 2 and reducing the entire polynomial mod $P(X)$ .
multiplicative inverse: (discussed below)

The definition says “the” binary finite field because the choice of $P(X)$ doesn't really matter. That's because, for each $k$ , there is only one finite field with $2^k$ elements. More precisely, if we use different choices of $P(X)$ in the definition above, then as long as they are both irreducible we will obtain fields that are isomorphic. There is only one mathematical field structure over $2^k$ elements, although there are many ways to encode the elements of that structure into strings.

Example .3 (Field addition)

To compute $\bit{11001} + \bit{01010}$ , add the corresponding polynomials and reduce mod 2:

\begin{array}{ll rrrrrr l} & \bit{11001} & \quad:\quad\text{} & X^4 & {}+X^3 & & & {}+1 \\ +{} & \bit{01010} & \quad:\quad\text{} & & X^3 & & {}+X & \\ \hline & & & X^4 & {}+2X^3 & & {}+X & {}+1 \\ ={} & \bit{10011} & \quad:\quad\text{} & X^4 & & & {}+X & {}+1 & \text{(reduce mod 2)} \end{array}

The result is $\bit{10011}$ .

Observation .4 (Field addition)

Addition in a binary finite field is just xor!

Example .5 (Field multiplication)

Let $P(X) = X^5 + X^2 + 1$ , which is irreducible. This example considers $GF(2^5)$ using this $P(X)$ as the polynomial modulus.

To compute $\bit{01001} \times \bit{01100}$ in the field, we do the following:

Multiply the polynomials:

$\underbrace{(X^3 + 1)}_{\bit{01001}} \times \underbrace{(X^3 + X^2)}_{\bit{01100}} = X^6 + X^5 + X^3 + X^2.$
Reduce mod $P(X)$ :

$\begin{aligned} X^6 + X^5 + X^3 + X^2 &= \hl{X^5} \cdot X + \hl{X^5} + X^3 + X^2 \\ &= (\hl{-X^2 - 1}) \cdot X + (\hl{-X^2 - 1}) + X^3 + X^2 \\ &= -X^3 - X - X^2 - 1 + X^3 + X^2 \\ &= -X - 1.\end{aligned}$
Reduce coefficients mod 2:

$-X -1 = X+1.$

The result is $\bit{00011}$ .

Observation .6 (Important field elements)

In the field $GF(2^k)$ , the element $\bit{0}^k$ represents the all-zeros polynomial and is the neutral element with respect to addition. We sometimes write it as “0.”

The element $\bit{0}^{n-1}\bit{1}$ represents the constant polynomial $A(X)=1$ , and is the neutral element with respect to multiplication. We sometimes write it as “1.”

Multiplicative inverses:

The most important property in a field is that every nonzero element has a multiplicative inverse:

Lemma .7 (Existence of inverses)

For every nonzero $A \in GF(2^k)$ , there is an element $A^{-1} \in GF(2^k)$ satisfying $A \cdot A^{-1} = 1$ .

We do not prove this fact here.

It is possible to efficiently compute inverses similarly to how they are computed for integers (section 3.4). Given $A$ , we can use a variant of the Euclidean GCD algorithm to compute the Bezout coefficients:

1 = \gcd( A, P ) = S\cdot A + T \cdot P,

where all the variables in this case are field elements (polynomials with 0/1 coefficients), and $P$ is the polynomial modulus. Since $P$ is an irreducible polynomial, and the degree of $A$ is less than that of $P$ , the GCD is indeed 1. Reducing both sides mod $P$ shows that $S$ must be the multiplicative inverse of $A$ .

Galois fields: There is nothing terribly special about reducing coefficients mod 2; it's merely the most convenient value for computers. It is also possible to construct a finite field with $\pmod^k$ elements for any prime $p$ and any $k\ge 1$ , by considering polynomials with coefficients in $\Z_\pmod$ , modulo an irreducible degree- $k$ polynomial. These are called Galois fields, after their discoverer. This is the reason for the notation $GF(\pmod^k)$ .

Sage: You can manipulate finite fields in sage:

Example .8 (Finite fields in Sage)

The following example establishes F as $GF(2^5)$ and sets X to be the formal variable of the field's polynomials. That way, you can use X to directly construct group elements. We can also see that sage has chosen the irreducible polynomial $X^5 + X^2 + 1$ as the modulus.

sage: F.<X> = GF(2^5) sage: F Finite Field in z5 of size 2^5 sage: F.modulus() X^5 + X^2 + 1 sage: X^11 X^2 + X + 1 sage: 1/X X^4 + X sage: X * (X^4 + X) 1

Applications to cryptography: Shamir secret sharing (construction 3.5.1) and poly-UHF (construction 11.4.1) were introduced using arithmetic modulo a prime. But the math behind these constructions works in any field, including the binary finite fields discussed here. Be careful not to get confused by the polynomials appearing at two levels of the abstraction:

We can use polynomials to define a finite field: The elements of the field are polynomials with coefficients mod $\pmod$ (mod 2 in the examples above); the field operations are essentially polynomial addition and multiplication mod $\pmod$ .
Equipped with a finite field, we should forget that the field elements are polynomials and simply think of the field as a collection of abstract objects that support addition, subtraction, multiplication, and division. Shamir secret sharing and poly-UHF then define polynomials over the field—that is, the coefficients are field elements and addition/multiplication that appear in the polynomial are the field operations.

Next Chapter1. One-Time Pad and the Provable Security Mindset

A Crash Course in Binary Finite Fields

Chapter Contents