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]: GF7([6, 0, 5, 2, 0, 1, 4, 3, 1, 6])

# 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]: GF7([2, 5, 4, 1, 4, 3, 3, 2, 6, 1])

# Addition in the finite field
In [5]: x + y
Out[5]: GF7([1, 5, 2, 3, 4, 4, 0, 5, 0, 0])

# Subtraction in the finite field
In [6]: x - y
Out[6]: GF7([4, 2, 1, 1, 3, 5, 1, 1, 2, 5])

# Multiplication in the finite field
In [7]: x * y
Out[7]: GF7([5, 0, 6, 2, 0, 3, 5, 6, 6, 6])

# Divison in the finite field
In [8]: x / y
Out[8]: GF7([3, 0, 3, 2, 0, 5, 6, 5, 6, 6])

In [9]: x // y
Out[9]: GF7([3, 0, 3, 2, 0, 5, 6, 5, 6, 6])

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]: 
GF7([[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]])

In [12]: X - Y
Out[12]: 
GF7([[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]])

In [13]: X * Y
Out[13]: 
GF7([[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]])

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

In [15]: X / Y
Out[15]: 
GF7([[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]])

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]: GF2^3([5, 6, 6, 0, 3, 3, 2, 0, 0, 6])

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

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]: GF7([4, 6, 6, 3, 1, 0, 6, 4, 3, 1])

# Calculates "x" * "x", note 2 is not a field element
In [24]: x ** 2
Out[24]: GF7([2, 1, 1, 2, 1, 0, 1, 2, 2, 1])

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]: GF7(3)

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

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

In [30]: GF7.alpha**e
Out[30]: GF7([5, 6, 6, 4, 2, 2, 4, 1, 3, 2])

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