Galois: A performant numpy extension for Galois fields¶
Installation¶
The latest version of galois can be installed from PyPI via pip.
pip3 install galois
The the lastest code from master can be checked out and installed locally in an “editable” fashion.
git clone https://github.com/mhostetter/galois.git
pip3 install -e galois
Basic Usage¶
Construct Galois field array classes using the GF_factory() class factory function.
In [1]: import numpy as np
In [2]: import galois
In [3]: GF = galois.GF_factory(31, 1)
In [4]: print(GF)
<Galois Field: GF(31^1), prim_poly = x + 28 (None decimal)>
In [5]: print(GF.alpha)
3
In [6]: print(GF.prim_poly)
Poly(x + 28 , GF31)
Create arrays from existing numpy arrays.
# Represents an existing numpy array
In [7]: array = np.random.randint(0, GF.order, 10, dtype=int); array
Out[7]: array([11, 14, 26, 28, 13, 28, 30, 20, 28, 9])
# Explicit Galois field construction
In [8]: GF(array)
Out[8]: GF31([11, 14, 26, 28, 13, 28, 30, 20, 28, 9])
# Numpy view casting to a Galois field
In [9]: array.view(GF)
Out[9]: GF31([11, 14, 26, 28, 13, 28, 30, 20, 28, 9])
Or, create Galois field arrays using alternate constructors.
In [10]: x = GF.Random(10); x
Out[10]: GF31([ 6, 12, 6, 14, 7, 17, 21, 17, 27, 17])
# Construct a random array without zeros to prevent ZeroDivisonError
In [11]: y = GF.Random(10, low=1); y
Out[11]: GF31([22, 4, 12, 11, 28, 21, 9, 29, 11, 6])
Galois field arrays support traditional numpy array operations
In [12]: x + y
Out[12]: GF31([28, 16, 18, 25, 4, 7, 30, 15, 7, 23])
In [13]: -x
Out[13]: GF31([25, 19, 25, 17, 24, 14, 10, 14, 4, 14])
# Multiply a Galois field array with any integer
In [14]: x * -3 # NOTE: -3 is outside the field
Out[14]: GF31([13, 26, 13, 20, 10, 11, 30, 11, 12, 11])
In [15]: 1 / y
Out[15]: GF31([24, 8, 13, 17, 10, 3, 7, 15, 17, 26])
# Exponentiate a Galois field array with any integer
In [16]: y ** -2 # NOTE: 87 is outside the field
Out[16]: GF31([18, 2, 14, 10, 7, 9, 18, 8, 10, 25])
# Log base alpha (the field's primitive element)
In [17]: np.log(y)
Out[17]: array([17, 18, 19, 23, 16, 29, 2, 9, 23, 25])
Galois field arrays support numpy array broadcasting.
In [18]: a = GF.Random((2,5)); a
Out[18]:
GF31([[ 0, 18, 5, 8, 0],
[16, 1, 28, 24, 14]])
In [19]: b = GF.Random(5); b
Out[19]: GF31([20, 28, 11, 15, 1])
In [20]: a + b
Out[20]:
GF31([[20, 15, 16, 23, 1],
[ 5, 29, 8, 8, 15]])
Galois field arrays also support numpy ufunc methods.
# Valid ufunc methods include "reduce", "accumulate", "reduceat", "outer", "at"
In [21]: np.multiply.reduce(a, axis=0)
Out[21]: GF31([ 0, 18, 16, 6, 0])
In [22]: np.multiply.outer(x, y)
Out[22]:
GF31([[ 8, 24, 10, 4, 13, 2, 23, 19, 4, 5],
[16, 17, 20, 8, 26, 4, 15, 7, 8, 10],
[ 8, 24, 10, 4, 13, 2, 23, 19, 4, 5],
[29, 25, 13, 30, 20, 15, 2, 3, 30, 22],
[30, 28, 22, 15, 10, 23, 1, 17, 15, 11],
[ 2, 6, 18, 1, 11, 16, 29, 28, 1, 9],
[28, 22, 4, 14, 30, 7, 3, 20, 14, 2],
[ 2, 6, 18, 1, 11, 16, 29, 28, 1, 9],
[ 5, 15, 14, 18, 12, 9, 26, 8, 18, 7],
[ 2, 6, 18, 1, 11, 16, 29, 28, 1, 9]])
Construct Galois field polynomials.
# Construct a polynomial by specifying all the coefficients in descending-degree order
In [23]: p = galois.Poly([1, 22, 0, 17, 25], field=GF); p
Out[23]: Poly(x^4 + 22x^3 + 17x + 25 , GF31)
# Construct a polynomial by specifying only the non-zero coefficients
In [24]: q = galois.Poly.NonZero([4, 14], [2, 0], field=GF); q
Out[24]: Poly(4x^2 + 14 , GF31)
Galois field polynomial arithmetic is similar to numpy array operations.
In [25]: p + q
Out[25]: Poly(x^4 + 22x^3 + 4x^2 + 17x + 8 , GF31)
In [26]: p // q, p % q
Out[26]: (Poly(8x^2 + 21x + 3 , GF31), Poly(2x + 14 , GF31))
In [27]: p ** 2
Out[27]: Poly(x^8 + 13x^7 + 19x^6 + 3x^5 + 23x^4 + 15x^3 + 10x^2 + 13x + 5 , GF31)
Galois field polynomials can also be evaluated at constants or arrays.
In [28]: p(1)
Out[28]: GF31(3)
In [29]: p(a)
Out[29]:
GF31([[25, 26, 13, 21, 25],
[15, 3, 19, 0, 2]])