Galois field array arithmetic

Addition, subtraction, multiplication, division

A finite field is a set that defines the operations addition, subtraction, multiplication, and division. The field is closed under these operations.

In [1]: GF7 = galois.GF_factory(7, 1)

In [2]: print(GF7)
<Galois Field: GF(7^1), prim_poly = x + 4 (11 decimal)>

# Create a random GF(7) array with 10 elements
In [3]: x = GF7.Random(10); x
Out[3]: GF([6, 0, 0, 1, 6, 4, 0, 3, 1, 3], order=7)

# Create a random GF(7) array with 10 elements, with the lowest element being 1 (used to prevent ZeroDivisionError later on)
In [4]: y = GF7.Random(10, low=1); y
Out[4]: GF([6, 3, 6, 4, 3, 5, 2, 1, 3, 4], order=7)

# Addition in the finite field
In [5]: x + y
Out[5]: GF([5, 3, 6, 5, 2, 2, 2, 4, 4, 0], order=7)

# Subtraction in the finite field
In [6]: x - y
Out[6]: GF([0, 4, 1, 4, 3, 6, 5, 2, 5, 6], order=7)

# Multiplication in the finite field
In [7]: x * y
Out[7]: GF([1, 0, 0, 4, 4, 6, 0, 3, 3, 5], order=7)

# Divison in the finite field
In [8]: x / y
Out[8]: GF([1, 0, 0, 2, 2, 5, 0, 3, 5, 6], order=7)

In [9]: x // y
Out[9]: GF([1, 0, 0, 2, 2, 5, 0, 3, 5, 6], order=7)

One can easily create the addition, subtraction, multiplication, and divison tables for any field. Here is an example using \(\mathrm{GF}(7)\).

In [10]: X, Y = np.meshgrid(GF7.Elements(), GF7.Elements(), indexing="ij")

In [11]: X + Y
Out[11]: 
GF([[0, 1, 2, 3, 4, 5, 6],
    [1, 2, 3, 4, 5, 6, 0],
    [2, 3, 4, 5, 6, 0, 1],
    [3, 4, 5, 6, 0, 1, 2],
    [4, 5, 6, 0, 1, 2, 3],
    [5, 6, 0, 1, 2, 3, 4],
    [6, 0, 1, 2, 3, 4, 5]], order=7)

In [12]: X - Y
Out[12]: 
GF([[0, 6, 5, 4, 3, 2, 1],
    [1, 0, 6, 5, 4, 3, 2],
    [2, 1, 0, 6, 5, 4, 3],
    [3, 2, 1, 0, 6, 5, 4],
    [4, 3, 2, 1, 0, 6, 5],
    [5, 4, 3, 2, 1, 0, 6],
    [6, 5, 4, 3, 2, 1, 0]], order=7)

In [13]: X * Y
Out[13]: 
GF([[0, 0, 0, 0, 0, 0, 0],
    [0, 1, 2, 3, 4, 5, 6],
    [0, 2, 4, 6, 1, 3, 5],
    [0, 3, 6, 2, 5, 1, 4],
    [0, 4, 1, 5, 2, 6, 3],
    [0, 5, 3, 1, 6, 4, 2],
    [0, 6, 5, 4, 3, 2, 1]], order=7)

In [14]: X, Y = np.meshgrid(GF7.Elements(), GF7.Elements()[1:], indexing="ij")

In [15]: X / Y
Out[15]: 
GF([[0, 0, 0, 0, 0, 0],
    [1, 4, 5, 2, 3, 6],
    [2, 1, 3, 4, 6, 5],
    [3, 5, 1, 6, 2, 4],
    [4, 2, 6, 1, 5, 3],
    [5, 6, 4, 3, 1, 2],
    [6, 3, 2, 5, 4, 1]], order=7)

Multiple addition

A finite field \(\mathrm{GF}(p^m)\) is a set that is closed under four operations: addition, subtraction, multiplication, and division. For multiplication, \(x * y = z\) for \(x, y, z \in \mathrm{GF}(p^m)\).

Let’s define another notation \(x \cdot r = z\) for \(x, z \in \mathrm{GF}(p^m)\) and \(r \in \mathbb{Z}\), which represents \(r\) additions of \(x\), i.e. \(x + \dotsb + x = z\). In prime fields \(\mathrm{GF}(p)\), multiplication \(*\) and “multiple addition” \(\cdot\) are equivalent. However, in extension fields \(\mathrm{GF}(p^m)\) they are not.

Warning

There is a difference between GF8(6) * GF8(2) and GF8(6) * 2. The former represents the field element “6” multiplied by the field element “2” using field multiplication. The latter represents adding the field element “6” two times.

In [16]: GF8 = galois.GF_factory(2, 3)

In [17]: print(GF8)
<Galois Field: GF(2^3), prim_poly = x^3 + x + 1 (11 decimal)>

In [18]: a = GF8.Random(10)

# Calculates a x "2" in the finite field
In [19]: a * GF8(2)
Out[19]: GF([7, 3, 7, 1, 3, 1, 6, 4, 0, 4], order=2^3)

# Calculates a + a
In [20]: a * 2
Out[20]: GF([0, 0, 0, 0, 0, 0, 0, 0, 0, 0], order=2^3)

Exponentiation

In [21]: GF7 = galois.GF_factory(7, 1)

In [22]: print(GF7)
<Galois Field: GF(7^1), prim_poly = x + 4 (11 decimal)>

In [23]: x = GF7.Random(10); x
Out[23]: GF([0, 5, 4, 2, 4, 4, 1, 2, 3, 5], order=7)

# Calculates "x" * "x", note 2 is not a field element
In [24]: x ** 2
Out[24]: GF([0, 4, 2, 4, 2, 2, 1, 4, 2, 4], order=7)

Logarithm

In [25]: GF7 = galois.GF_factory(7, 1)

In [26]: print(GF7)
<Galois Field: GF(7^1), prim_poly = x + 4 (11 decimal)>

# The primitive element of the field
In [27]: GF7.alpha
Out[27]: GF(3, order=7)

In [28]: x = GF7.Random(10, low=1); x
Out[28]: GF([5, 1, 2, 5, 3, 2, 4, 4, 2, 2], order=7)

# Notice the outputs of log(x) are not field elements, but integers
In [29]: e = np.log(x); e
Out[29]: array([5, 0, 2, 5, 1, 2, 4, 4, 2, 2])

In [30]: GF7.alpha**e
Out[30]: GF([5, 1, 2, 5, 3, 2, 4, 4, 2, 2], order=7)

In [31]: np.all(GF7.alpha**e == x)
Out[31]: True