readme.md

title	tags
27. Finite Field	zk abstract algebra field finite field Galois field

WTF zk Tutorial Lesson 27: Finite Field

In this chapter, we will introduce finite fields (also known as Galois fields), which are fields that contain a finite number of elements. They are often used in cryptography and zero-knowledge proof algorithms.

1. Finite Field

A finite field, also known as a Galois field (named after Galois, the founder of modern group theory), is a field that contains a finite number of elements. We usually denote a finite field with $GF(q)$ or $F_q$, where $q$ is the number of elements in the field.

Property 1: The number of elements in a finite field can only be a prime number $p$ or a power of a prime $p^n$. A field with $p$ elements is called a prime field, and a field with $p^n$ elements is called an extension field of the prime field.

2. Prime Field

The most common type of finite field is the prime field $GF(p)$ (also written as $F_p$), which is the field of integers modulo $p$. This type of finite field is also called a prime field. You can think of a prime field as the remainder classes of integers modulo $p$, where addition and multiplication are performed modulo $p$.

For example, the finite field $GF(2)$ (also written as $F_2$) contains two elements ${0, 1}$, which can represent 1 bit. Its addition table and multiplication table are as follows:

$GF(2)$ addition table

+	0	1
0	0	1
1	1	0

$GF(2)$ multiplication table

·	0	1
0	0	0
1	0	1

Another example is the finite field $GF(3)$, which contains three elements ${0,1,2}$. Its addition table and multiplication table are as follows:

$GF(3)$ addition table

+	0	1	2
0	0	1	2
1	1	2	0
2	2	0	1

$GF(3)$ multiplication table

·	0	1	2
0	0	0	0
1	0	1	2
2	0	2	1

Here are some properties of prime fields:

Property 2: The characteristic of a prime field $F_p$ is $p$. This means that $1 \cdot p = 0$, and any element multiplied by $p$ is also equal to the zero element.

For example, the characteristic of $F_p$ is $3$, and we have

$$ 0 \cdot 3 = 0 \pmod{3} $$

$$ 1 \cdot 3 = 0 \pmod{3} $$

$$ 2 \cdot 3 = 0 \pmod{3} $$

Property 3: Any finite field with $p$ elements is isomorphic to the prime field $F_p$.

This means that we can use the prime field $F_p$ to study other finite fields with $p$ elements, as they are essentially the same.

3. Field Extension

A field extension of a prime field is a field of order $p^n$, where $p^n$ is a power of a prime, and it extends the prime field $F_p$.

Construction Method: Suppose $F_p$ is a prime field, $f(x)$ is an irreducible polynomial of degree $n$ over $F_p$, and $(f(x))$ is the principal ideal generated by $f(x)$. Then, the quotient ring $F_{p^n} = F[x]/(f(x))$ is a finite field of order $p^n$, consisting of all polynomials of degree less than $n$ in the polynomial ring $F[x]$:

$$ F_{p^n} = {a_{n-1}x^{n-1} + ... + a_0 | a_i \in F_p} $$

Addition in the finite field $F_{p^n}$ is performed in the polynomial ring, and multiplication is performed in the polynomial ring followed by division by the irreducible polynomial $f(x)$ to ensure that the degree of the result does not exceed $n$.

Since each coefficient of a polynomial in the finite field $F_{p^n}$ has $p$ choices, and there are $n$ coefficients in total, $F_{p^n}$ has a total of $p^n$ elements.

Also, since each coefficient belongs to $Z_p$, the characteristic of the finite field $F_{p^n}$ is $p$.

For example, let's construct the finite field $F_4$. Since $4 = 2^2$, we construct it using $F_2 = {0,1}$. First, we find an irreducible polynomial of degree 2 from the polynomial ring $F_2[x]$:

$$ x^2 + x + 1 $$

Then, we construct the quotient ring $F_2[x]/(x^2 + x + 1)$, which is $F_4$, where the elements are the equivalence classes of polynomials in $F_2[x]$ that are congruent to $x^2 + x + 1$.

The elements in this finite field can be represented as $a + b \alpha$, where $a, b \in F_2$ and $\alpha$ is a root of $x^2 + x + 1$. The constructed finite field can be represented as:

$$ {0, 1, \alpha, 1 + \alpha} $$

Originally, it was ${0, 1, \alpha, \alpha^2}$, but $\alpha^2 = -\alpha -1 = \alpha + 1$. The addition and multiplication operations in the finite field $F_4$ are performed in $F_2[x]/(x^2 + x + 1)$, modulo the congruence relation of $x^2 + x + 1$.

4. Code Implementation

We can use the galois package to implement finite fields in Python. In the following program, we construct a finite field $GF(4)$ and print its properties, elements, addition table, and multiplication table:

import galois

GF4 = galois.GF(4)
print("Properties of the finite field GF(4):", GF4.properties)
print("Elements of the finite field GF(4):", GF4.elements)

print("Addition table of the finite field GF(4)")
print(GF4.arithmetic_table("+"))
print("Multiplication table of the finite field GF(4)")
print(GF4.arithmetic_table("*"))

## Output Example
# Properties of the finite field GF(4): Galois Field:
#   name: GF(2^2)
#   characteristic: 2
#   degree: 2
#   order: 4
#   irreducible_poly: x^2 + x + 1
#   is_primitive_poly: True
#   primitive_element: x
# Elements of the finite field GF(4): [0 1 2 3]
# Addition table of the finite field GF(4)
# x + y | 0  1  2  3 
# ------|------------
#     0 | 0  1  2  3 
#     1 | 1  0  3  2 
#     2 | 2  3  0  1 
#     3 | 3  2  1  0 
# Multiplication table of the finite field GF(4)
# x * y | 0  1  2  3 
# ------|------------
#     0 | 0  0  0  0 
#     1 | 0  1  2  3 
#     2 | 0  2  3  1 
#     3 | 0  3  1  2 

5. Summary

In this chapter, we introduced finite fields, which are the most commonly used mathematical structures in cryptography and zero-knowledge proofs. Finite fields include prime fields and their extension fields: a prime field $F_p$ is the simplest type of finite field, consisting of $p$ elements; a field extension of the prime field contains $q^n$ elements, constructed based on the prime field $F_p$ and an irreducible polynomial.