# Galois field array arithmetic¶

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(7)

In [2]: print(GF7)
<class 'numpy.ndarray over GF(7)'>

# Create a random GF(7) array with 10 elements
In [3]: x = GF7.Random(10); x
Out[3]: GF([4, 2, 0, 0, 3, 4, 0, 5, 6, 2], 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, 5, 4, 6, 4, 5, 6, 6, 2, 6], order=7)

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

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

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

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

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


One can easily create the addition, subtraction, multiplication, and division 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)


## Scalar multiplication¶

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 for scalar multiplication. For $$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 scalar multiplication are equivalent. However, in extension fields $$\mathrm{GF}(p^m)$$ they are not.

Warning

In the extension field $$\mathrm{GF}(2^3)$$, 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 finite field multiplication. The latter represents adding the field element “6” two times.

In [16]: GF8 = galois.GF(2**3)

In [17]: a = GF8.Random(10); a
Out[17]: GF([0, 6, 1, 7, 0, 2, 0, 6, 6, 2], order=2^3)

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

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


In prime fields $$\mathrm{GF}(p)$$, multiplication and scalar multiplication are equivalent.

In [20]: GF7 = galois.GF(7)

In [21]: a = GF7.Random(10); a
Out[21]: GF([4, 0, 6, 6, 6, 6, 2, 0, 4, 1], order=7)

# Calculates a x "2" in the finite field
In [22]: a * GF7(2)
Out[22]: GF([1, 0, 5, 5, 5, 5, 4, 0, 1, 2], order=7)

# Calculates a + a
In [23]: a * 2
Out[23]: GF([1, 0, 5, 5, 5, 5, 4, 0, 1, 2], order=7)


## Exponentiation¶

In [24]: GF7 = galois.GF(7)

In [25]: print(GF7)
<class 'numpy.ndarray over GF(7)'>

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

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


## Logarithm¶

In [28]: GF7 = galois.GF(7)

In [29]: print(GF7)
<class 'numpy.ndarray over GF(7)'>

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

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

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

In [33]: GF7.primitive_element**e
Out[33]: GF([5, 4, 3, 6, 4, 5, 6, 3, 2, 2], order=7)

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