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
Tutorials¶
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 (59 decimal)>
In [5]: print(GF.alpha)
GF31(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([ 5, 11, 23, 19, 11, 14, 24, 5, 26, 27])
# Explicit Galois field construction
In [8]: GF(array)
Out[8]: GF31([ 5, 11, 23, 19, 11, 14, 24, 5, 26, 27])
# Numpy view casting to a Galois field
In [9]: array.view(GF)
Out[9]: GF31([ 5, 11, 23, 19, 11, 14, 24, 5, 26, 27])
Or, create Galois field arrays using alternate constructors.
In [10]: x = GF.Random(10); x
Out[10]: GF31([17, 5, 23, 24, 21, 9, 27, 3, 7, 25])
# Construct a random array without zeros to prevent ZeroDivisonError
In [11]: y = GF.Random(10, low=1); y
Out[11]: GF31([30, 20, 1, 8, 25, 15, 4, 22, 20, 1])
Galois field arrays support traditional numpy array operations
In [12]: x + y
Out[12]: GF31([16, 25, 24, 1, 15, 24, 0, 25, 27, 26])
In [13]: -x
Out[13]: GF31([14, 26, 8, 7, 10, 22, 4, 28, 24, 6])
In [14]: x * y
Out[14]: GF31([14, 7, 23, 6, 29, 11, 15, 4, 16, 25])
In [15]: x / y
Out[15]: GF31([14, 8, 23, 3, 12, 13, 30, 10, 5, 25])
# Multiple addition of a Galois field array with any integer
In [16]: x * -3 # NOTE: -3 is outside the field
Out[16]: GF31([11, 16, 24, 21, 30, 4, 12, 22, 10, 18])
# Exponentiate a Galois field array with any integer
In [17]: y ** -2 # NOTE: 87 is outside the field
Out[17]: GF31([ 1, 10, 1, 16, 25, 4, 2, 18, 10, 1])
# Log base alpha (the field's primitive element)
In [18]: np.log(y)
Out[18]: array([15, 8, 0, 12, 10, 21, 18, 17, 8, 0])
Galois field arrays support numpy array broadcasting.
In [19]: a = GF.Random((2,5)); a
Out[19]:
GF31([[18, 30, 29, 0, 1],
[23, 26, 1, 3, 1]])
In [20]: b = GF.Random(5); b
Out[20]: GF31([28, 22, 19, 14, 3])
In [21]: a + b
Out[21]:
GF31([[15, 21, 17, 14, 4],
[20, 17, 20, 17, 4]])
Galois field arrays also support numpy ufunc methods.
# Valid ufunc methods include "reduce", "accumulate", "reduceat", "outer", "at"
In [22]: np.multiply.reduce(a, axis=0)
Out[22]: GF31([11, 5, 29, 0, 1])
In [23]: np.multiply.outer(x, y)
Out[23]:
GF31([[14, 30, 17, 12, 22, 7, 6, 2, 30, 17],
[26, 7, 5, 9, 1, 13, 20, 17, 7, 5],
[ 8, 26, 23, 29, 17, 4, 30, 10, 26, 23],
[ 7, 15, 24, 6, 11, 19, 3, 1, 15, 24],
[10, 17, 21, 13, 29, 5, 22, 28, 17, 21],
[22, 25, 9, 10, 8, 11, 5, 12, 25, 9],
[ 4, 13, 27, 30, 24, 2, 15, 5, 13, 27],
[28, 29, 3, 24, 13, 14, 12, 4, 29, 3],
[24, 16, 7, 25, 20, 12, 28, 30, 16, 7],
[ 6, 4, 25, 14, 5, 3, 7, 23, 4, 25]])
Construct Galois field polynomials.
# Construct a polynomial by specifying all the coefficients in descending-degree order
In [24]: p = galois.Poly([1, 22, 0, 17, 25], field=GF); p
Out[24]: Poly(x^4 + 22x^3 + 17x + 25, GF31)
# Construct a polynomial by specifying only the non-zero coefficients
In [25]: q = galois.Poly.NonZero([4, 14], [2, 0], field=GF); q
Out[25]: Poly(4x^2 + 14, GF31)
Galois field polynomial arithmetic is similar to numpy array operations.
In [26]: p + q
Out[26]: Poly(x^4 + 22x^3 + 4x^2 + 17x + 8, GF31)
In [27]: p // q, p % q
Out[27]: (Poly(8x^2 + 21x + 3, GF31), Poly(2x + 14, GF31))
In [28]: p ** 2
Out[28]: 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 [29]: p(1)
Out[29]: GF31(3)
In [30]: p(a)
Out[30]:
GF31([[26, 18, 17, 25, 3],
[ 6, 16, 3, 7, 3]])