Galois Fields — GF(2^n)
In 1831, Évariste Galois 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, and simply our bit operations.
As we have seen from the previous podcasts, that we map from one set to another for encryption, and then reverse back for decryption. For example, we might multiply by 15 and add 7. To map back, we will then subtract by 7 and divide by 15. But, what happens if we need to constrain the values of our integers into a given number of bits and perform simple modulo-2 operations?
A Galois field
Within a field, we can operate on values in the field using arithmetic operations. We can thus have an infinite field and where we could include all of the possible integers. A Galois field of GF(p^n) has p^n elements. Typically we use GF(2^n). And so GF(2⁴) has 16 values in the field. Let’s say we have GF(2^n) and have a number a∈{0,…,2^n−1}, we can represent it as a vector in the form of a polynomial:
