Array Arithmetic¶
After creating a Galois field array class and one or two Galois field arrays, nearly any arithmetic operation can be performed using normal NumPy ufuncs or Python operators.
In the sections below, the finite field \(\mathrm{GF}(3^5)\) and arrays \(x\) and \(y\) are used.
In [1]: GF = galois.GF(3**5)
In [2]: x = GF([184, 25, 157, 31]); x
Out[2]: GF([184, 25, 157, 31], order=3^5)
In [3]: y = GF([179, 9, 139, 27]); y
Out[3]: GF([179, 9, 139, 27], order=3^5)
Ufuncs¶
NumPy ufuncs are universal functions that operate on scalars. Unary ufuncs operate on a single scalar and binary ufuncs operate on two scalars. NumPy extends the scalar operation of ufuncs to operate on arrays in various ways. This extensibility enables NumPy broadcasting.
Expand any section for more details.
Addition: x + y == np.add(x, y)
In [4]: x + y
Out[4]: GF([ 81, 7, 215, 58], order=3^5)
In [5]: np.add(x, y)
Out[5]: GF([ 81, 7, 215, 58], order=3^5)
Additive inverse: -x == np.negative(x)
In [6]: -x
Out[6]: GF([ 98, 14, 206, 62], order=3^5)
In [7]: np.negative(x)
Out[7]: GF([ 98, 14, 206, 62], order=3^5)
Any array added to its additive inverse results in zero.
In [8]: x + np.negative(x)
Out[8]: GF([0, 0, 0, 0], order=3^5)
Subtraction: x - y == np.subtract(x, y)
In [9]: x - y
Out[9]: GF([17, 16, 18, 4], order=3^5)
In [10]: np.subtract(x, y)
Out[10]: GF([17, 16, 18, 4], order=3^5)
Multiplication: x * y == np.multiply(x, y)
In [11]: x * y
Out[11]: GF([ 41, 225, 106, 123], order=3^5)
In [12]: np.multiply(x, y)
Out[12]: GF([ 41, 225, 106, 123], order=3^5)
Scalar multiplication: x * z == np.multiply(x, z)
Scalar multiplication is essentially repeated addition. It is the “multiplication” of finite field elements and integers. The integer value indicates how many additions of the field element to sum.
In [13]: x * 4
Out[13]: GF([184, 25, 157, 31], order=3^5)
In [14]: np.multiply(x, 4)
Out[14]: GF([184, 25, 157, 31], order=3^5)
In [15]: x + x + x + x
Out[15]: GF([184, 25, 157, 31], order=3^5)
In finite fields \(\mathrm{GF}(p^m)\), the characteristic \(p\) is the smallest value when multiplied by any non-zero field element that results in \(0\).
In [16]: p = GF.characteristic; p
Out[16]: 3
In [17]: x * p
Out[17]: GF([0, 0, 0, 0], order=3^5)
Multiplicative inverse: y ** -1 == np.reciprocal(y)
In [18]: y ** -1
Out[18]: GF([ 71, 217, 213, 235], order=3^5)
In [19]: GF(1) / y
Out[19]: GF([ 71, 217, 213, 235], order=3^5)
In [20]: np.reciprocal(y)
Out[20]: GF([ 71, 217, 213, 235], order=3^5)
Any array multiplied by its multiplicative inverse results in one.
In [21]: y * np.reciprocal(y)
Out[21]: GF([1, 1, 1, 1], order=3^5)
Division: x / y == x // y == np.divide(x, y)
In [22]: x / y
Out[22]: GF([237, 56, 122, 126], order=3^5)
In [23]: x // y
Out[23]: GF([237, 56, 122, 126], order=3^5)
In [24]: np.divide(x, y)
Out[24]: GF([237, 56, 122, 126], order=3^5)
Remainder: x % y == np.remainder(x, y)
In [25]: x % y
Out[25]: GF([0, 0, 0, 0], order=3^5)
In [26]: np.remainder(x, y)
Out[26]: GF([0, 0, 0, 0], order=3^5)
Divmod: divmod(x, y) == np.divmod(x, y)
In [27]: x / y, x % y
Out[27]: (GF([237, 56, 122, 126], order=3^5), GF([0, 0, 0, 0], order=3^5))
In [28]: divmod(x, y)
Out[28]: (GF([237, 56, 122, 126], order=3^5), GF([0, 0, 0, 0], order=3^5))
In [29]: np.divmod(x, y)
Out[29]: (GF([237, 56, 122, 126], order=3^5), GF([0, 0, 0, 0], order=3^5))
In [30]: q, r = divmod(x, y)
In [31]: q*y + r == x
Out[31]: array([ True, True, True, True])
Exponentiation: x ** z == np.power(x, z)
In [32]: x ** 3
Out[32]: GF([175, 76, 218, 192], order=3^5)
In [33]: np.power(x, 3)
Out[33]: GF([175, 76, 218, 192], order=3^5)
In [34]: x * x * x
Out[34]: GF([175, 76, 218, 192], order=3^5)
Square root: np.sqrt(x)
# Ensure the elements of x have square roots
In [35]: x.is_quadratic_residue()
Out[35]: array([ True, True, True, True])
In [36]: z = np.sqrt(x); z
Out[36]: GF([102, 109, 14, 111], order=3^5)
In [37]: z ** 2 == x
Out[37]: array([ True, True, True, True])
Logarithm: np.log(x)
In [38]: z = np.log(y); z
Out[38]: array([60, 2, 59, 3])
In [39]: α = GF.primitive_element; α
Out[39]: GF(3, order=3^5)
In [40]: α ** z == y
Out[40]: array([ True, True, True, True])
Ufunc methods¶
Galois field arrays support NumPy ufunc methods. Ufunc methods allow a user to apply a NumPy ufunc in a unique way across the target array. All arithmetic ufuncs are supported.
Expand any section for more details.
reduce()
The numpy.ufunc.reduce methods reduce the input array’s dimension by one, applying the ufunc across one axis.
In [41]: np.add.reduce(x)
Out[41]: GF(7, order=3^5)
In [42]: x[0] + x[1] + x[2] + x[3]
Out[42]: GF(7, order=3^5)
In [43]: np.multiply.reduce(x)
Out[43]: GF(105, order=3^5)
In [44]: x[0] * x[1] * x[2] * x[3]
Out[44]: GF(105, order=3^5)
accumulate()
The numpy.ufunc.accumulate methods accumulate the result of the ufunc across a specified axis.
In [45]: np.add.accumulate(x)
Out[45]: GF([184, 173, 57, 7], order=3^5)
In [46]: GF([x[0], x[0] + x[1], x[0] + x[1] + x[2], x[0] + x[1] + x[2] + x[3]])
Out[46]: GF([184, 173, 57, 7], order=3^5)
In [47]: np.multiply.accumulate(x)
Out[47]: GF([184, 9, 211, 105], order=3^5)
In [48]: GF([x[0], x[0] * x[1], x[0] * x[1] * x[2], x[0] * x[1] * x[2] * x[3]])
Out[48]: GF([184, 9, 211, 105], order=3^5)
reduceat()
The numpy.ufunc.reduceat methods reduces the input array’s dimension by one, applying the ufunc across one axis
in-between certain indices.
In [49]: np.add.reduceat(x, [0, 3])
Out[49]: GF([57, 31], order=3^5)
In [50]: GF([x[0] + x[1] + x[2], x[3]])
Out[50]: GF([57, 31], order=3^5)
In [51]: np.multiply.reduceat(x, [0, 3])
Out[51]: GF([211, 31], order=3^5)
In [52]: GF([x[0] * x[1] * x[2], x[3]])
Out[52]: GF([211, 31], order=3^5)
outer()
The numpy.ufunc.outer methods applies the ufunc to each pair of inputs.
In [53]: np.add.outer(x, y)
Out[53]:
GF([[ 81, 166, 80, 211],
[165, 7, 155, 52],
[ 54, 139, 215, 103],
[198, 40, 89, 58]], order=3^5)
In [54]: np.multiply.outer(x, y)
Out[54]:
GF([[ 41, 192, 93, 97],
[ 91, 225, 193, 196],
[ 80, 211, 106, 145],
[149, 41, 129, 123]], order=3^5)
at()
The numpy.ufunc.at methods performs the ufunc in-place at the specified indices.
In [55]: z = x.copy()
# Negate indices 0 and 1 in-place
In [56]: np.negative.at(x, [0, 1]); x
Out[56]: GF([ 98, 14, 157, 31], order=3^5)
In [57]: z[0:1] *= -1; z
Out[57]: GF([ 98, 25, 157, 31], order=3^5)
Advanced arithmetic¶
Convolution: np.convolve(x, y)
In [58]: np.convolve(x, y)
Out[58]: GF([ 79, 80, 5, 79, 167, 166, 123], order=3^5)