Finite Fields (Galois Field)

Finite field basicsSearch on YouTubeBookmarkSaved

DefinitionSearch on YouTubeBookmarkSaved

A finite field is also called a Galois field. The course notes name the mathematician "Pierre Galois". His real name is Évariste Galois. A Galois field with $q$ elements has the name $GF(q)$.

A finite field has these formal properties:

• It has two defined operations: addition and multiplication.
• The sum or product of two field elements is always a field element (closure).
• It has a zero element: $a + 0 = a$.
• It has a unity element: $a \cdot 1 = a$.
• Each element $a$ has an additive inverse $-a$, with $a + (-a) = 0$. Subtraction is addition of the inverse.
• Each non-zero element $b$ has a multiplicative inverse $b^{-1}$, with $b \cdot b^{-1} = 1$. Division is multiplication by the inverse.
• The associative, commutative and distributive laws apply.

$$a+(b+c)=(a+b)+c, \quad a\cdot(b\cdot c)=(a\cdot b)\cdot c, \quad a\cdot(b+c)=a\cdot b+a\cdot c$$

Field sizesSearch on YouTubeBookmarkSaved

Not all field sizes can satisfy these properties. They are satisfied when the field size is a prime number or an integer power of a prime.

Prime size field GF(p)Search on YouTubeBookmarkSaved

Arithmetic modulo pSearch on YouTubeBookmarkSaved

For a field with a prime number $p$ of elements, do the arithmetic modulo $p$. Take two elements in the range $0$ to $p-1$. Add or multiply them. Then take the result modulo $p$.

• GF(2): modulo-2 addition and multiplication. The elements are 0 and 1.
• GF(3): the elements are 0, 1 and 2.

In GF(3), the additive inverse of 0 is 0. The additive inverse of 1 is 2, and the additive inverse of 2 is 1. To find a multiplicative inverse, find the pair of elements with product 1 in the table. In GF(3), $1^{-1} = 1$ and $2^{-1} = 2$, because $2 \cdot 2 = 4 \equiv 1 \pmod 3$.

Primitive elementSearch on YouTubeBookmarkSaved

In each prime size field, at least one element has powers that give all the non-zero elements. This element is primitive. In $GF(7)$, the number 3 is primitive:

$$3^1=3,\ 3^2=2,\ 3^3=6,\ 3^4=4,\ 3^5=5,\ 3^6=1 \pmod 7$$

Higher powers of 3 repeat the pattern, because $3^6 = 1$. You can multiply two elements if you add their powers of 3:

$$6 \times 2 = 3^3 \times 3^2 = 3^5 = 5$$

The multiplicative inverse of $3^i$ is $3^{-i} = 3^{6-i}$. In GF(7):

• The inverse of $6$ ($3^3$) is $6$ ($3^3$).
• The inverse of $4$ ($3^4$) is $2$ ($3^2$).
• The inverse of $5$ ($3^5$) is $3$ ($3^1$).

GF(7) subtraction and divisionSearch on YouTubeBookmarkSaved

Example 3 builds the addition and multiplication tables of GF(7) with the elements 0 to 6. Use the addition table also for subtraction. Use the multiplication table for division.

• Subtract 6 from 3. The additive inverse of 6 is 1. Thus $3 - 6 = 3 + 1 = 4$.
• Divide 3 by 2. The multiplicative inverse of 2 is 4. Thus $3 \div 2 = 3 \cdot 4 = 12 \equiv 5$.

Polynomials over GF(2)Search on YouTubeBookmarkSaved

Degree and countSearch on YouTubeBookmarkSaved

A polynomial over GF(2) has coefficients from GF(2):

$$f(X) = f_0 + f_1 X + f_2 X^2 + \cdots + f_n X^n, \qquad f_i = 0 \text{ or } 1$$

The degree is the largest power of $X$ with a non-zero coefficient. If $f_n = 1$, $f(X)$ has degree $n$. The degree of $f(X) = f_0$ is zero.

• Degree 1 has two polynomials: $X$ and $1 + X$.
• Degree 2 has four polynomials: $X^2$, $1 + X^2$, $X + X^2$ and $1 + X + X^2$.
• In general, degree $n$ has $2^n$ polynomials.

AdditionSearch on YouTubeBookmarkSaved

To add $f(X)$ and $g(X)$, add the coefficients of the same power of $X$ modulo 2. Subtraction gives the same result, because $1 + 1 = 0$.

DivisionSearch on YouTubeBookmarkSaved

When you divide $f(X)$ by $g(X)$, you get one pair of polynomials: the quotient $q(X)$ and the remainder $r(X)$:

$$f(X) = q(X)\,g(X) + r(X), \qquad \deg r(X) < \deg g(X)$$

Example 7. Divide $f(X) = 1 + X + X^4 + X^5 + X^6$ by $g(X) = 1 + X + X^3$.

1. $X^6 \div X^3 = X^3$. Subtract $X^3 g(X) = X^6 + X^4 + X^3$. The result is $X^5 + X^3 + X + 1$.
2. $X^5 \div X^3 = X^2$. Subtract $X^2 g(X) = X^5 + X^3 + X^2$. The result is $X^2 + X + 1$.
3. The degree is now less than 3, so the division stops.

$$q(X) = X^3 + X^2, \qquad r(X) = X^2 + X + 1$$

Check: $X^6 + X^5 + X^4 + X + 1 = (X^3 + X^2)(X^3 + X + 1) + X^2 + X + 1$.

If $r(X) = 0$, then $f(X)$ is divisible by $g(X)$, and $g(X)$ is a factor of $f(X)$.

Roots and the X + 1 factorSearch on YouTubeBookmarkSaved

For real numbers, if $a$ is a root of $f(X)$, then $f(X)$ is divisible by $X - a$. The same rule applies over GF(2).

Example 8. Let $f(X) = 1 + X^2 + X^3 + X^4$. Put $X = 1$:

$$f(1) = 1 + 1 + 1 + 1 = 0$$

Thus 1 is a root, and $f(X)$ is divisible by $X + 1$. The long division gives:

$$X^4 + X^3 + X^2 + 1 = (X + 1)(X^3 + X + 1)$$

Irreducible polynomialsSearch on YouTubeBookmarkSaved

DefinitionSearch on YouTubeBookmarkSaved

A polynomial $p(X)$ over GF(2) of degree $m$ is irreducible if it has no factor of lower degree. The factor degree must be greater than zero and less than $m$.

Example 9. Check the four polynomials of degree 2:

• $X^2$ and $X^2 + X$ are divisible by $X$.
• $X^2 + 1$ is divisible by $X + 1$.
• $X^2 + X + 1$ has no root at 0 or 1. Thus no degree-1 polynomial divides it. It is irreducible.

Divisor of X^(2^m - 1) + 1Search on YouTubeBookmarkSaved

For each $m \geq 1$, an irreducible polynomial of degree $m$ exists that divides $X^{2^m - 1} + 1$.

Example 10. $X^3 + X + 1$ divides $X^{2^3 - 1} + 1 = X^7 + 1$. The long division gives:

$$X^7 + 1 = (X^3 + X + 1)(X^4 + X^2 + X + 1)$$

Primitive polynomialsSearch on YouTubeBookmarkSaved

DefinitionSearch on YouTubeBookmarkSaved

An irreducible polynomial $p(X)$ of degree $m$ is primitive if the smallest positive $n$ for which $p(X)$ divides $X^n + 1$ is $n = 2^m - 1$.

• $X^4 + X + 1$ divides $X^{15} + 1$. It does not divide $X^n + 1$ for $1 \leq n < 15$. Thus it is primitive.
• $X^4 + X^3 + X^2 + X + 1$ is irreducible. It divides $X^5 + 1$, so it is not primitive.

Primitive polynomial tableSearch on YouTubeBookmarkSaved

It is not easy to find a primitive polynomial. Tables of irreducible polynomials show which ones are primitive. One degree $m$ can have more than one primitive polynomial. Some entries from the table in the notes:

Construction of GF(2^m)Search on YouTubeBookmarkSaved

Powers of alphaSearch on YouTubeBookmarkSaved

Start with the elements 0 and 1 from GF(2) and a new symbol $\alpha$. Define a multiplication "$\cdot$" with these rules:

$$0 \cdot \alpha^j = 0, \qquad 1 \cdot \alpha^j = \alpha^j, \qquad \alpha^i \cdot \alpha^j = \alpha^{i+j}$$

Here $\alpha^j = \alpha \cdot \alpha \cdots \alpha$ ($j$ times). This gives the set:

$$F = \{0, 1, \alpha, \alpha^2, \ldots, \alpha^j, \ldots\}$$

Closing the setSearch on YouTubeBookmarkSaved

Let $p(X)$ be a primitive polynomial of degree $m$, and set $p(\alpha) = 0$. Because $p(X)$ divides $X^{2^m - 1} + 1$:

$$X^{2^m - 1} + 1 = q(X)\,p(X)$$

Put $X = \alpha$. Because $p(\alpha) = 0$, the right side is 0. Thus:

$$\alpha^{2^m - 1} + 1 = 0 \quad \Rightarrow \quad \alpha^{2^m - 1} = 1$$

The powers repeat after $2^m - 1$ steps. The set becomes finite:

$$F^* = \{0, 1, \alpha, \alpha^2, \ldots, \alpha^{2^m - 2}\}$$

$F^*$ is a Galois field of $2^m$ elements, $GF(2^m)$. GF(2) is a subfield of $GF(2^m)$.

GF(2^4) exampleSearch on YouTubeBookmarkSaved

Example 11. Let $m = 4$ and $p(X) = 1 + X + X^4$, a primitive polynomial. Set $p(\alpha) = 0$. Then:

$$\alpha^4 = 1 + \alpha$$

Use this identity again and again to write each power as a polynomial of degree 3 or less:

The next power is $\alpha^{15} = 1$. The field has 15 non-zero elements and 0, so it has 16 elements.

Roots in GF(2^m)Search on YouTubeBookmarkSaved

Roots in an extension fieldSearch on YouTubeBookmarkSaved

A polynomial with real coefficients can have roots that are not real. An example is $X^2 + 6X + 25$, with the complex roots $-3 + 4j$ and $-3 - 4j$. Similarly, a polynomial over GF(2) can have no roots in GF(2), but have roots in an extension field of GF(2).

Example 12. $X^4 + X^3 + 1$ is irreducible over GF(2), so it has no roots in GF(2). It has four roots in $GF(2^4)$: $\alpha^7$, $\alpha^{11}$, $\alpha^{13}$ and $\alpha^{14}$. To verify, multiply out the product with the GF(16) table:

$$(X + \alpha^7)(X + \alpha^{11})(X + \alpha^{13})(X + \alpha^{14}) = X^4 + X^3 + 1$$

ConjugatesSearch on YouTubeBookmarkSaved

Let $f(X)$ be a polynomial over GF(2), and let $\beta$ be an element in an extension field of GF(2). If $\beta$ is a root of $f(X)$, then $\beta^{2^l}$ is also a root for each $l \geq 0$. The element $\beta^{2^l}$ is a conjugate of $\beta$.

Example. $f(X) = 1 + X^3 + X^4 + X^5 + X^6$ has $\alpha^4$ as a root. With $\alpha^{15} = 1$:

$$f(\alpha^4) = 1 + \alpha^{12} + \alpha + \alpha^5 + \alpha^9 = 1 + (1 + \alpha + \alpha^2 + \alpha^3) + \alpha + (\alpha + \alpha^2) + (\alpha + \alpha^3) = 0$$

The conjugates of $\alpha^4$ are $\alpha^8$, $\alpha^{16} = \alpha$ and $\alpha^{32} = \alpha^2$. Thus $\alpha^8$, $\alpha$ and $\alpha^2$ are also roots of $f(X)$. The element $\alpha^5$ and its conjugate $\alpha^{10}$ are also roots.

Roots of X^(2^m - 1) + 1Search on YouTubeBookmarkSaved

Let $\beta$ be a non-zero element of $GF(2^m)$. Then $\beta^{2^m - 1} = 1$, so $\beta^{2^m - 1} + 1 = 0$. Thus each non-zero element of $GF(2^m)$ is a root of $X^{2^m - 1} + 1$. This polynomial has degree $2^m - 1$. Thus the $2^m - 1$ non-zero elements are all its roots.

Minimal polynomialsSearch on YouTubeBookmarkSaved

Definition and rulesSearch on YouTubeBookmarkSaved

The minimal polynomial $\phi(X)$ of a field element $\beta$ is the polynomial of smallest degree over GF(2) with $\beta$ as a root.

• The minimal polynomial of a field element is irreducible.
• Let $\beta$ be a root of a polynomial $f(X)$ over GF(2). Then $f(X)$ is divisible by $\phi(X)$.
• An element and its conjugates have the same minimal polynomial.

Minimal polynomial of alpha^3Search on YouTubeBookmarkSaved

Example 13. In $GF(2^4)$, let $\beta = \alpha^3$. The conjugates are $\beta^2 = \alpha^6$, $\beta^{4} = \alpha^{12}$ and $\beta^{8} = \alpha^{24} = \alpha^9$. Thus:

$$\phi(X) = (X + \alpha^3)(X + \alpha^6)(X + \alpha^{12})(X + \alpha^9)$$

Multiply out the product with the GF(16) table:

$$\phi(X) = (X^2 + \alpha^2 X + \alpha^9)(X^2 + \alpha^8 X + \alpha^6) = X^4 + X^3 + X^2 + X + 1$$

Minimal polynomials of GF(2^4)Search on YouTubeBookmarkSaved

The minimal polynomials of all elements in $GF(2^4)$, made by $p(X) = X^4 + X + 1$:

Link to AESSearch on YouTubeBookmarkSaved

AES uses $GF(2^8)$, which is made in the same way. It uses the irreducible polynomial:

$$m(x) = x^8 + x^4 + x^3 + x + 1 = \{11B\}$$

The AES S-box and MixColumns do their calculations in this field. The AES lecture shows the five roles of field arithmetic in the cipher.

Quick self-testSearch on YouTubeBookmarkSaved

Which field sizes give a finite field?

A prime number or an integer power of a prime. AES uses $2^8$, a power of the prime 2.

Calculate 3 − 6 and 3 ÷ 2 in GF(7).

The additive inverse of 6 is 1, so $3 - 6 = 3 + 1 = 4$. The multiplicative inverse of 2 is 4, so $3 \div 2 = 3 \cdot 4 = 12 \equiv 5$.

Why is 3 primitive in GF(7)?

The powers $3^1$ to $3^6$ give 3, 2, 6, 4, 5, 1. These are all six non-zero elements.

Divide $1 + X + X^4 + X^5 + X^6$ by $1 + X + X^3$ over GF(2).

The quotient is $X^3 + X^2$. The remainder is $X^2 + X + 1$.

Is $1 + X^2 + X^3 + X^4$ divisible by $X + 1$?

Yes. It has an even number of terms, so $f(1) = 0$. The quotient is $X^3 + X + 1$.

Which degree-2 polynomial over GF(2) is irreducible?

Only $X^2 + X + 1$. It has no root at 0 or 1. $X^2$ and $X^2 + X$ are divisible by $X$. $X^2 + 1$ is divisible by $X + 1$.

Why is $X^4 + X + 1$ primitive, but $X^4 + X^3 + X^2 + X + 1$ is not?

$X^4 + X + 1$ first divides $X^n + 1$ at $n = 15 = 2^4 - 1$. The other polynomial already divides $X^5 + 1$.

How do you build GF(16) from $p(X) = 1 + X + X^4$?

Set $p(\alpha) = 0$, so $\alpha^4 = 1 + \alpha$. Use this identity to write $\alpha^0$ to $\alpha^{14}$ as polynomials of degree 3 or less. Then $\alpha^{15} = 1$, and the field has 16 elements with 0.

What are the conjugates of $\alpha^3$ in GF(16), and what is its minimal polynomial?

The conjugates are $\alpha^6$, $\alpha^{12}$ and $\alpha^9$. The minimal polynomial is $X^4 + X^3 + X^2 + X + 1$.

Give the roots of $X^4 + X^3 + 1$ in GF(16).

$\alpha^7$, $\alpha^{11}$, $\alpha^{13}$ and $\alpha^{14}$. They are conjugates of each other.