Finite Field

Modulo operation

Given $a, m, r \in \Z$, $m > 0$, and $0 \le r \le m-1$, we write

$$a\ \text{mod}\ m \equiv r$$

when $m$ divides $a-r$ (also denoted as $m | (a-r)$). Here, $r$ is referred to as the remainder.

Example

Given $a=17, m=5$, find r.

One possible answer is $r=2$ because $17 \mod 5 \equiv 2$. This is because 5|(17-2), which is read as 5 divided by 15.

For the example above, we can find many other remainders, such as 7 and -3. This is because 5|(17-7) and 5|(17+3).

Finite field

A finite field is a field with a finite number of elements. Finite fields have many applications in data science and especially in cryptography. We usually define a finite field using modulo operation.

Galois field

A finite field having prime number of elements over mod $p$ is called a Galois field or prime field. A Galois field is usually referred to as $GF(p)$, where $p$ is a prime number and $GF(p)=\{0, 1, \cdots, p-1\}$.

Example

A set $S=\{0,1,2,3,4\}$ defined over mod $5$ makes a Galois field $GF(5)$. This implies that after each operation on field, we apply mod $5$ on the result. For instance,

$$2+4 \equiv 6 \mod 5 \equiv 1$$

and

$$2\times 4 \equiv 8 \mod 5 \equiv 3$$

Let’s now provide verification of each property using Python code.

Axiom verification

We can prove the axiom verification by using mathematical arguments, but let’s verify it through code and test all the properties of the field $S$.

Closure

We define the sum function, which computes the sum of two elements of a field and then computes mod 5 of the result. We first make a list of the elements, S=[0,1,2,3,4], and then use itertools to generate all possible pairs. The following code calls the sum function on every possible pair of elements of S, verifying the closure axiom. Similarly, we can test the closure under multiplication using mul, which also first multiplies two numbers and then takes their modulus.

Below is the complete code for testing closure under $+$ and $\times$.