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

• Exponentiation is defined within a group as a repeated application of the group operator, so that \(a^3 = a \cdot a \cdot a\).

• We define \(a^0 = e\) as the identity element, and \(a^{-n} = (a')^n\) , where \(a'\) is the inverse element of \(a\) within the group.

• A group \(G\) is cyclic if every element of \(G\) is a power \(a^k\) (\(k\) is an integer) of a fixed element \(a \in G\).

• The element \(a\) is said to generate the group \(G\) or to be a generator of \(G\).

• A cyclic group is always abelian and may be finite or infinite.

Rings

• A ring \(R\), sometimes denoted by \(\lbrace R , + , \times \rbrace\), is a set of elements with two binary operations, called addition and multiplication, such that for all \(a , b , c \in R\) the axioms (A1-A5) are obeyed.

• \(R\) is an abelian group with respect to addition; that is, \(R\) satisfies axioms A1 through A5. For the case of an additive group, we denote the identity element as \(0\) and the inverse of \(a\) as \(–a\).

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

• A ring is said to be commutative if it satisfies the following additional condition:

  (M4) Commutativity of multiplication:

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

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

• A field \(F\), sometimes denoted by \(\lbrace F, +, \times \rbrace\), is a set of elements with two binary operations, called addition and multiplication, such that for all \(a, b, c \in F\) the axioms (A1–M6) are obeyed.

• \(F\) is an integral domain; that is, \(F\) satisfies axioms A1 through A5 and M1 through M6

(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

• In essence, a field is a set in which we can do addition, subtraction, multiplication, and division without leaving the set. Division is defined with the following rule: \(a/b = a (b^{-1})\)

Summary - Properties of Groups, Rings and Fields

Types of Fields

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

• Finite fields play a crucial role in many cryptographic algorithms.

• It can be shown that the order of a finite field must be a power of a prime \(p^n\), where \(n\) is a positive integer.

• The finite field of order \(p^n\) is generally written \(GF(p^n)\).

• GF stands for Galois field, in honor of the mathematician who first studied finite fields.

Addition Modulo 8

Multiplication Modulo 8

Additive and muliplicative inverses modulo 8

Addition modulo 7

Multiplication modulo 7

Additive and muliplicative inverses modulo 7

The Field GF(2)

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

(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\)

• If each distinct polynomial is considered to be an element of the set, then that set is a ring.

• When polynomial arithmetic is performed on polynomials over a field, then division is possible.

• If we attempt to perform polynomial division over a coefficient set that is not a field, we find that division is not always defined.

  • Even if the coefficient set is a field, polynomial division is not necessarily exact

  • With the understanding that remainders are allowed, we can say that polynomial division is possible if the coefficient set is a field

Polynomial Division

• We can write any polynomial in the form: \(f(x) = q(x) g(x) + r(x)\)

  • \(r(x)\) can be interpreted as being a remainder

  • So \(r(x) = f(x)\; mod\; g(x)\)

• If there is no remainder we can say \(g(x)\) divides \(f(x)\)

  • Written as \(g(x) | f(x)\)

  • We can say that \(g(x)\) is a factor of \(f(x)\)

  • Or \(g(x)\) is a divisor of \(f(x)\)

• A polynomial \(f(x)\) over a field \(F\) is called irreducible if and only if \(f(x)\) cannot be expressed as a product of two polynomials, both over \(F\), and both of degree lower than that of \(f(x)\).

  • An irreducible polynomial is also called a prime polynomial.

• Polynomial divsion can be defined in terms of multiplication if \(a,b \in F\) then \(a/b = a \times b^{-1}\) where \(b^{-1}\) is the unique field element such that \(bb^{-1} = 1\).

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

• The polynomial \(c(x)\) is said to be the greatest common divisor of \(a(x)\) and \(b(x)\) if the following are true:

  • \(c(x)\) divides both \(a(x)\) and \(b(x)\)

  • Any divisor of \(a(x)\) and \(b(x)\) is a divisor of \(c(x)\)

• An equivalent definition is:

  • \(gcd[a(x), b(x)]\) is the polynomial of maximum degree that divides both \(a(x)\) and \(b(x)\)

• The Euclidean algorithm can be extended to find the greatest common divisor of two polynomials whose coefficients are elements of a field.

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

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

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

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)\).

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

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

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

• No simple operation will achieve multiplication in \(GF(2^n)\).

• However, a reasonable straightforward technique is available.

Computational Considerations

• Since coefficients are 0 or 1, they can represent any such polynomial as a bit string

  • Addition becomes XOR of these bit strings

  • Multiplication is shift and XOR

    (cf long-hand multiplication)

• Modulo reduction is done by repeatedly substituting highest power with remainder of irreducible polynomial (also shift and XOR)