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(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([3, 1, 5, 0, 0, 2, 5, 6, 2, 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([5, 5, 1, 6, 3, 2, 3, 1, 6, 2], order=7)

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

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

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

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

In [9]: x // y
Out[9]: GF([2, 3, 5, 0, 0, 1, 4, 6, 5, 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^8)\), 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([1, 6, 5, 6, 1, 5, 4, 3, 7, 0], order=2^3)

# Calculates a x "2" in the finite field
In [18]: a * GF8(2)
Out[18]: GF([2, 7, 1, 7, 2, 1, 3, 6, 5, 0], 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([2, 2, 6, 0, 3, 5, 6, 5, 1, 4], order=7)

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

# Calculates a + a
In [23]: a * 2
Out[23]: GF([4, 4, 5, 0, 6, 3, 5, 3, 2, 1], 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([0, 3, 5, 1, 3, 4, 5, 0, 3, 1], order=7)

# Calculates "x" * "x", note 2 is not a field element
In [27]: x ** 2
Out[27]: GF([0, 2, 4, 1, 2, 2, 4, 0, 2, 1], 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([1, 3, 5, 2, 3, 1, 3, 6, 3, 3], order=7)

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

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

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