Finite Fields

Lecturer:

Prof. Dr. Michael Eichberg

Version:
2023-10-19
Based on:

Cryptography and Network Security - Principles and Practice, 8th Edition, William Stallings

Groups, Rings and Fields

((((((
    Finite Fields
        in Fields)
            in Integral Domains)
                in Commutative Rings)
                    in Rings)
                        in Abelian Groups)
                            in Groups)

Groups

A set of elements with a binary operation \(\cdot\) that associates to each ordered pair \((a,b)\) of elements in \(G\) an element \((a \cdot b ) \in G\) , such that the following axioms are obeyed:

(A1) Closure:

If \(a\) and \(b\) belong to \(G\), then \(a \cdot b\) is also in \(G\)

(A2) Associative:

\(a \cdot ( b \cdot c ) = ( a \cdot b ) \cdot c\) for all \(a, b, c \in G\)

(A3) Identity element:

There is an element \(e \in G\) such that \(a \cdot e = e \cdot a = a\) for all \(a \in G\)

(A4) Inverse element:

For each \(a \in G\), there is an element \(a'\) in G such that \(a \cdot a' = a' \cdot a = e\)

Abelian Group

(A1 through A4) and:

(A5) Commutative:

\(a \cdot b = b \cdot a\) for all \(a, b \in G\)

Cyclic Group

Rings

Rings

(M1) Closure under multiplication:

If \(a\) and \(b\) belong to \(R\), then \(ab\) is also in \(R\)

(M2) Associativity of multiplication:

\(a(bc) = (ab)c\) for all \(a,b,c \in R\)

(M3) Distributive laws:

\(a(b+c) = ab+ac\) for all \(a,b,c \in R\)

\((a+b)c = ac+bc\) for all \(a,b,c \in R\)

In essence, a ring is a set in which we can do addition, subtraction \([a - b = a + (-b )]\), and multiplication without leaving the set.

Rings

Integral Domain Integritätsring

A commutative ring that obeys the following axioms.

(M5) Multiplicative identity:

There is an element \(1\) in \(R\) such that \(a1 = 1a = a\) for all \(a \in R\)

(M6) No zero divisors:

If \(a,b \in R\) and \(ab = 0\), then either \(a = 0\) or \(b = 0\)

Fields Körper

(M7) Multiplicative inverse:

For each \(a\) in \(F\), except \(0\), there is an element \(a^{-1} \in F\) such that \(aa^{-1} = (a^{-1})a = 1\)

Fields

Summary - Properties of Groups, Rings and Fields

Properties of Groups, Rings, and Fields

Types of Fields

4-types_of_fields.svg

Finite Fields of the Form \(GF(p)\)

Addition Modulo 8

\(+\)

0

1

2

3

4

5

6

7

0

0

1

2

3

4

5

6

7

1

1

2

3

4

5

6

7

0

2

2

3

4

5

6

7

0

1

3

3

4

5

6

7

0

1

2

4

4

5

6

7

0

1

2

3

5

5

6

7

0

1

2

3

4

6

6

7

0

1

2

3

4

5

7

7

0

1

2

3

4

5

6

Multiplication Modulo 8

\(\times\)

0

1

2

3

4

5

6

7

0

0

0

0

0

0

0

0

0

1

0

1

2

3

4

5

6

7

2

0

2

4

6

0

2

4

6

3

0

3

6

1

4

7

2

5

4

0

4

0

4

0

4

0

4

5

0

5

2

7

4

1

6

3

6

0

6

4

2

0

6

4

2

7

0

7

6

5

4

3

2

1

Additive and muliplicative inverses modulo 8

\(w\)

\(-w\)

\(w^{-1}\)

0

0

\(-\)

1

7

1

2

6

\(-\)

3

5

3

4

4

\(-\)

5

3

5

6

2

\(-\)

7

1

7

Addition modulo 7

\(+\)

0

1

2

3

4

5

6

0

0

1

2

3

4

5

6

1

1

2

3

4

5

6

0

2

2

3

4

5

6

0

1

3

3

4

5

6

0

1

2

4

4

5

6

0

1

2

3

5

5

6

0

1

2

3

4

6

6

0

1

2

3

4

5

Multiplication modulo 7

\(\times\)

0

1

2

3

4

5

6

0

0

0

0

0

0

0

0

1

0

1

2

3

4

5

6

2

0

2

4

6

1

3

5

3

0

3

6

2

5

1

4

4

0

4

1

5

2

6

3

5

0

5

3

1

6

4

2

6

0

6

5

4

3

2

1

Additive and muliplicative inverses modulo 7

\(w\)

\(-w\)

\(w^{-1}\)

0

0

\(-\)

1

6

1

2

5

4

3

4

5

4

3

2

5

2

3

6

1

6

The Field GF(2)

Addition

\(+\)

0

1

0

0

1

1

1

0

Multiplication

\(\times\)

0

1

0

0

0

1

0

1

Inverses

\(w\)

\(-w\)

\(w^{-1}\)

0

0

0

1

0

1

Finite Fields

In this section, we have shown how to construct finite fields of order \(p\) where \(p\) is prim.

\(GF(p)\) is defined with the following properties:

  1. \(GF(p)\) consists of \(p\) elements

  2. The binary operations \(+\) and \(\times\) are defined over the set. The operations of addition, subtraction, multiplication, and division can be performed without leaving the set. Each element of the set other than 0 has a multiplicative inverse.

Treatment of Polynomials

Treatment of Polynomials

(indeterminate unbestimmte)

Example of Ordinary Polynomial Arithmetic

Addition:
\begin{equation*} (x^3 + x^2 + 2) + (x^2 - x + 1) = x^3 + 2x^2 - x + 3 \end{equation*}
Subtraction:
\begin{equation*} (x^3 + x^2 + 2) - (x^2 - x + 1) = x^3 + x + 1 \end{equation*}
Multiplication:
\begin{equation*} (x^3 + x^2 + 2) \times (x^2 - x + 1) = \end{equation*}
\begin{equation*} \begin{matrix} & & & & x^3 & + & x^2 & & & + & 2 \\ & - & x^4 & - & x^3 & & & - & 2x & & & \\ x^5 & + & x^4 & & & + & 2x^2 & & & & & = \end{matrix} \end{equation*}
\begin{equation*} x^{5} + 3x^2 - 2x + 2 \end{equation*}
Division:
\begin{equation*} (x^3 + x^2 + 2) : (x^2 - x + 1) = x + 2 + \left ( \frac{x}{x^2 - x + 1} \right ) \end{equation*}

Polynomial Arithmetic with Coefficients in \(Z_p\)

Polynomial Division

Example of Polynomial Arithmetic Over GF(2)

Addition:
\begin{equation*} (x^7 + x^5 + x^4 + x^3 + x + 1) + (x^3 + x + 1) = x^7 + x^5 + x^4 \end{equation*}
Subtraction:
\begin{equation*} (x^7 + x^5 + x^4 + x^3 + x + 1) - (x^3 + x + 1) = x^7 + x^5 + x^4 \end{equation*}

Example of Polynomial Arithmetic Over GF(2)

Multiplication:
\begin{equation*} (x^7 + x^5 + x^4 + x^3 + x + 1) \times (x^3 + x + 1) = \end{equation*}
\begin{equation*} \begin{matrix} & & & & & & x^7 & + & & & x^5 & +& x^4 & + & x^3 & + & & & x & + & 1 \\ & & & & x^8 & + & & & x^6 & + & x^5 & + & x^4 &+ & & & x^2 & + & x & & & \\ x^{10} & + & & & x^8 & + & x^7 & + & x^6 & + & & & x^4 & + & x^3 & & & & & & & = \end{matrix} \end{equation*}
\begin{equation*} x^{10} + x^4 +x^2 +1 \end{equation*}
Division:
\begin{equation*} (x^7 + x^5 + x^4 + x^3 + x + 1) : (x^3 + x + 1) = x^4 + 1 \end{equation*}

Polynomial GCD

Arithmetic in \(GF(2^3)\): Addition (by means of XOR)

000

001

010

011

100

101

110

111

\(+\)

0

1

2

3

4

5

6

7

000

0

0

1

2

3

4

5

6

7

001

1

1

0

3

2

5

4

7

6

010

2

2

3

0

1

6

7

4

5

011

3

3

2

1

0

7

6

5

4

100

4

4

5

6

7

0

1

2

3

101

5

5

4

7

6

1

0

3

2

110

6

6

7

4

5

2

3

0

1

111

7

7

6

5

4

3

2

1

0

Arithmetic in \(GF(2^3)\): Multiplication

000

001

010

011

100

101

110

111

\(\times\)

0

1

2

3

4

5

6

7

000

0

0

0

0

0

0

0

0

0

001

1

0

1

2

3

4

5

6

7

010

2

0

2

4

6

3

1

7

5

011

3

0

3

6

5

7

4

1

2

100

4

0

4

3

7

6

2

5

1

101

5

0

5

1

4

2

7

3

6

110

6

0

6

7

1

5

3

2

4

111

7

0

7

5

2

1

6

4

3

Arithmetic in \(GF(2^3)\): Additive and Multiplicative Inverses

\(w\)

\(-w\)

\(w^{-1}\)

0

0

\(-\)

1

1

1

2

2

5

3

3

6

4

4

7

5

5

2

6

6

3

7

7

4

Polynomial Arithmetic in \(GF(2^3)\)

To construct the finite field \(GF(2^3)\), we need to chose an irreducible polynomial of degree 3. I.e., either \((x^3+x^2+1)\) or \((x^3+x+1)\).

With multiplications modulo x^3 + x + 1, we have only the following eight polynomials in the set of polynomials over \(GF(2)\):

\begin{equation*} 0, 1, x, x^2, x+1, x^2 + 1, x^2 + x, x^2 + x + 1 \end{equation*}

Polynomial Arithmetic in \(GF(2^3)\) Modulo \((x^3 + x + 1)\)

Addition

000

001

010

011

100

101

110

111

\(+\)

0

1

\(x\)

\(x+1\)

\(x^2\)

\(x^2+1\)

\(x^2+x\)

\(x^2+x+1\)

000

0

0

1

x

\(x+1\)

\(x^2\)

\(x^2 + 1\)

\(x^2 + x\)

\(x^2 + x + 1\)

001

1

1

0

\(x+1\)

x

\(x^2 + 1\)

\(x^2\)

\(x^2 + x + 1\)

\(x^2 + x\)

010

\(x\)

x

\(x+1\)

0

1

\(x^2 + x\)

\(x^2 + x + 1\)

\(x^2\)

\(x^2 + 1\)

011

\(x+1\)

\(x+1\)

x

1

0

\(x^2 + x + 1\)

\(x^2 + x\)

\(x^2 + 1\)

\(x^2\)

100

\(x^2\)

\(x^2\)

\(x^2 + 1\)

\(x^2 + x\)

\(x^2 + x + 1\)

0

1

x

\(x+1\)

101

\(x^2+1\)

\(x^2 + 1\)

\(x^2\)

\(x^2 + x + 1\)

\(x^2 + x\)

1

0

\(x+1\)

x

110

\(x^2+x\)

\(x^2 + x\)

\(x^2 + x + 1\)

\(x^2\)

\(x^2 + 1\)

x

\(x+1\)

0

1

111

\(x^2+x+1\)

\(x^2 + x + 1\)

\(x^2 + x\)

\(x^2 + 1\)

\(x^2\)

\(x+1\)

x

1

0

Polynomial Arithmetic in \(GF(2^3)\) Modulo \((x^3 + x + 1)\)

Multiplication

000

001

010

011

100

101

110

111

\(\times\)

0

1

\(x\)

\(x+1\)

\(x^2\)

\(x^2+1\)

\(x^2+x\)

\(x^2+x+1\)

000

0

0

0

0

0

0

0

0

0

001

1

0

1

\(x\)

\(x+1\)

\(x^2\)

\(x^2 + 1\)

\(x^2 + x\)

\(x^2 + x + 1\)

010

\(x\)

0

\(x\)

\(x^2\)

\(x^2 + x\)

\(x+1\)

1

\(x^2 + x + 1\)

\(x^2 + 1\)

011

\(x+1\)

0

\(x+1\)

\(x^2 + x\)

\(x^2 + 1\)

\(x^2 + x + 1\)

\(x^2\)

1

\(x\)

100

\(x^2\)

0

\(x^2\)

\(x+1\)

\(x^2 + x + 1\)

\(x^2 + x\)

\(x\)

\(x^2 + 1\)

1

101

\(x^2+1\)

0

\(x^2 + 1\)

1

\(x^2\)

\(x\)

\(x^2 + x + 1\)

\(x+1\)

\(x^2 + x\)

110

\(x^2+x\)

0

\(x^2 + x\)

\(x^2 + x + 1\)

1

\(x^2 + 1\)

\(x+1\)

\(x\)

\(x^2\)

111

\(x^2+x+1\)

0

\(x^2 + x + 1\)

\(x^2 + 1\)

\(x\)

1

\(x^2 + x\)

\(x^2\)

\(x+1\)

Multiplication in \(GF(2^n)\)

Computational Considerations