Galois Field: Comprehensive Guide and Python Implementation

Galois fields are collectively refer to as finite fields.

Here are several heuristic Galois field implementations.

Mod based Galois field

Let's define GF(10000), 10000 means all the operation results will fall into the range of 0-9999

Addition and Subtraction

Define mod operator as %.

• Add

Given a and b, find c = a + b.

a = 4321
b = 9432
field_range = 10000
assert a < field_range and b < field_range, f'a and b must both under {field_range}'

c = (a+b) % field_range
print(c) 
# c = 3753

• Subtract

Given b and c, find a = c - b.

b = 9432
c = 3753
field_range = 10000

a = (c-b) % field_range
print(a)
# a = 4321

Given a and c, find b = c - a.

a = 4321
c = 3753
field_range = 10000

b = (c-a) % field_range
print(b)
# b = 9432

The best way to understand it is to imagine you are in a train having infinite carriages.

Everytime you move from seat No.9999 forward 1 step, you arrived the first seat(No.0000) of next carriage.

print((9999+1) % 10000)
# 0

Similarly, if you move from seat No.0000 backward 1 step, you got the last seat(No.9999) of previous carriage.

print((0-1) % 10000)
# 9999

That's exactly how %(mod operator) works. +(addition) means how many steps you got to move forward; -(subtraction) means how many steps you got to move backward;

Multiplication and Division

• Multiplication

Also use mod operator, formula: (a*b) % field_range.

a = 123
b = 456
field_range = 10000
assert a < field_range and b < field_range, f'a and b must both under {field_range}'

mc = (a*b) % field_range
print(mc)
# 6088

• Division

Given a and c, find b = c / a.

From:

c = a * b

c = mc + field_range*n

We can get:

b = c / a

b = (mc + field_range*n) / a

One way to get b is trying every possible n in field_range, until we find the b that satisfy condition.

def get_n_range(mc, field_range, a):
    minimum = -mc / field_range
    maximum = (a * field_range - mc) / field_range
    return minimum, maximum

a = 2
b = None
mc = 6
field_range = 10

minimum, maximum = get_n_range(mc, field_range, a)
for i in range(math.floor(minimum), math.ceil(maximum)):
    if (mc + field_range*i) % a == 0:
        b = (mc + field_range*i) // a
        if b > field_range:
            break
        if 0 < b < field_range:
            print(b)
# 3
# 8

Is mod based Galois field one-to-one mapping?

Meaning, for a * b % field_range, is there only one b that satisfy the condition?

To prove this, just raise an example where (a * b1) % field_range = (a * (b1+theta)) % field_range exists.

How to fast calculate b?

Given:

• a = 7
• mc = 5
• field_range = 19
• mc = (a*b) % field_range

Find b.

1. b = (mc + field_range*N) / a and b is a unique integer.
2. (mc + field_range*N) % a = 0
3. mc % a = field_range*n % a
   • n = -N
4. 1 % a = field_range*k % a
   • k = n / mc
5. 1 % 7 = 19*k % 7
6. 19k + 7y % 7 = 19*k % 7, construct a formula where k, y meet this condition.
7. 19k + 7y = 1, use Extended Euclidean algorithm to solve this equation.

Got k = 3, so:

• n = k*mc = 3*5 = 15.
• N = -15
• b = (mc + field_range*N) / a
• b = (5 + 19*(-15)) / 7
• b = -40
• b = -40 % 19
• b = 17

Test it:

a = 7
b = 17
field_range = 19
mc = 5

assert mc == a*b % field_range

Polynomial based Galois Field

Similar theory can be extended to polynomial.

Addition, Subtraction and Multiplication

Similar with normal polynomial operations, so we can skip this part.

Division and Mod

In polynomial based Galois field, division and mod are all using Long Division to result.

Let's define $GF(x^2-1)$, which means all the operation results will be mod by this polynomial: $P = x^2-1$.

Given:

• $a = x^5+3x^2$
• $P = x^2-1$

Find $a \mod P$.

So in result we got:

• $a / P = x^3-x+3$
• $a \mod P = -x+3$

Is polynomial based Galois field one-to-one mapping?

Similar with mod based Galois field, we can prove it by raising an example where (a * b1) % field_range = (a * (b1+theta)) % field_range exists.

Which equals to a * theta % field_range = 0, so a must be a factor of field_range.

So, only when field_range is a prime polynomial, the Galois field will be one-to-one mapping.

When will a polynomial be a prime polynomial?

A polynomial is a prime polynomial if it is irreducible, which means it cannot be factored into the product of two non-constant polynomials, like $x^2 -1 = (x+1)(x-1)$

Which equals to the plot of this polynomial won't cross x-axis. Here is an example:

GF(N^m)

For example, if N=3, m=5, then we can define a Galois field with 3^5=243 elements, whose polynomial form is: $a_4x^4 + a_3x^2 + a_2x^2 + a_1x + a_0$ , where $a_i \in \{0, 1, 2\}$.

All the arithmetic operations are similar with polynomial based Galois field. If the coefficient overflows, we can use mod operation to keep it in the range of 0-2.

GF(2^😎

GF(2^8) is widely used in cryptography, where the typical polynomial is x^8 + x^4 + x^3 + x + 1.

The reason why GF(2^8) is widely used is because it can be implemented by a byte, which is very convenient for computer to process.

Addition and Subtraction

Since GF(2^8) is a binary field, so the addition and subtraction can be simply implemented by XOR operation. For example:

• $a = x^7 + x^6 + x^4 + x^2 + 1 = 0b11010101$
• $b = x^7 + x^5 + x^3 + x^2 + 1 = 0b10101101$

Then:

• $c = a + b = 0b11010101 \oplus 0b10101101 = 0b01111000$

Multiplication and Division

The most efficient way to implement multiplication and division in GF(2^8) is to use lookup table.

For GF(2^8), the multiplication and division can be implemented respectively by a 256x256 lookup table, where the element in row i and column j is the result of i * j.

Appendix

Implementations

Mod Based Galois Field

class GaloisField:
    def __init__(self, value, p):
        self.value = value % p
        self.p = p

    def __add__(self, other):
        if isinstance(other, GaloisField):
            if self.p != other.p:
                raise ValueError("Cannot add two numbers from different fields")
            return GaloisField((self.value + other.value) % self.p, self.p)
        return GaloisField((self.value + other) % self.p, self.p)
    
    def __sub__(self, other):
        if isinstance(other, GaloisField):
            if self.p != other.p:
                raise ValueError("Cannot subtract two numbers from different fields")
            return GaloisField((self.value - other.value) % self.p, self.p)
        return GaloisField((self.value - other) % self.p, self.p)
    
    def __mul__(self, other):
        if isinstance(other, GaloisField):
            if self.p != other.p:
                raise ValueError("Cannot multiply two numbers from different fields")
            return GaloisField((self.value * other.value) % self.p, self.p)
        return GaloisField((self.value * other) % self.p, self.p)
    
    def __truediv__(self, other):
        if isinstance(other, GaloisField):
            if self.p != other.p:
                raise ValueError("Cannot divide two numbers from different fields")
            return self * other.inverse()
        return self * GaloisField(other, self.p).inverse()
    
    def inverse(self):
        # Use the Extended Euclidean Algorithm to find the multiplicative inverse
        t, newt = 0, 1
        r, newr = self.p, self.value
        while newr != 0:
            quotient = r // newr
            t, newt = newt, t - quotient * newt
            r, newr = newr, r - quotient * newr
        if r > 1:
            raise ValueError(f"{self.value} has no multiplicative inverse modulo {self.p}")
        if t < 0:
            t = t + self.p
        return GaloisField(t, self.p)
    
    def __repr__(self):
        return f"GF({self.value}, {self.p})"

# Example usage:
a = GaloisField(5, 11)
b = GaloisField(7, 11)

print(a + b)  # GaloisField(6 mod 7)
print(a - b)  # GaloisField(0 mod 7)
print(a * b)  # GaloisField(2 mod 7)
print(a / b)  # GaloisField(5 mod 7)

Polynomial Based Galois Field

# nothing