The Galois field (GF)

On 30 May in 1832, Évariste Galois — pronounced Gal-wha — died of duelling wounds at the age of 20 but left a great legacy. While he was a teenager he worked on polynomials and laid down the principles of Galois theory, along with defining the concept of a finite field. In cryptography, the finite field is one of the major concepts and involves limiting the number of possible values to a limiting factor (p). The values of the field then range from 0 to p-1.

Z_p (mod p)

First, let’s start with the problem. In finite fields, we have a (mod n) operation for a list of integers (Z), and where n is a prime number. This works for our add (+) and multiply (*) operations, and where:

a (mod n) + b (mod n) = (a+b) (mod n)

a (mod n) *b (mod n) = (a*b) (mod n)

If we take Z_7, we get [here]:

Additive group for Z_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 

Multiplicative group for Z_7
+ | 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