Basic Usage
The main idea of the galois
package can be summarized as follows. The user creates a “Galois field array class” using GF = galois.GF(p**m)
.
A Galois field array class GF
is a subclass of numpy.ndarray
and its constructor x = GF(array_like)
mimics
the call signature of numpy.array()
. A Galois field array x
is operated on like any other NumPy array, but all
arithmetic is performed in \(\mathrm{GF}(p^m)\) not \(\mathbb{Z}\) or \(\mathbb{R}\).
Internally, the Galois field arithmetic is implemented by replacing NumPy ufuncs. The new ufuncs are written in Python and then just-in-time compiled with Numba. The ufuncs can be configured to use either lookup tables (for speed) or explicit calculation (for memory savings).
Galois field arrays
Class construction
Galois field array classes are created using the galois.GF()
class factory function.
In [1]: import numpy as np
In [2]: import galois
In [3]: GF256 = galois.GF(2**8)
In [4]: print(GF256)
<class 'numpy.ndarray over GF(2^8)'>
These classes are subclasses of galois.FieldArray
(which itself subclasses numpy.ndarray
) and have galois.FieldClass
as their metaclass.
In [5]: isinstance(GF256, galois.FieldClass)
Out[5]: True
In [6]: issubclass(GF256, galois.FieldArray)
Out[6]: True
In [7]: issubclass(GF256, np.ndarray)
Out[7]: True
A Galois field array class contains attributes relating to its Galois field and methods to modify how the field
is calculated or displayed. See the attributes and methods in galois.FieldClass
.
# Summarizes some properties of the Galois field
In [8]: print(GF256.properties)
GF(2^8):
characteristic: 2
degree: 8
order: 256
irreducible_poly: x^8 + x^4 + x^3 + x^2 + 1
is_primitive_poly: True
primitive_element: x
# Access each attribute individually
In [9]: GF256.irreducible_poly
Out[9]: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2))
The galois
package even supports arbitrarily-large fields! This is accomplished by using NumPy arrays
with dtype=object
and pure-Python ufuncs. This comes at a performance penalty compared to smaller fields
which use NumPy integer dtypes (e.g., numpy.uint32
) and have compiled ufuncs.
In [10]: GF = galois.GF(36893488147419103183); print(GF.properties)
GF(36893488147419103183):
characteristic: 36893488147419103183
degree: 1
order: 36893488147419103183
irreducible_poly: x + 36893488147419103180
is_primitive_poly: True
primitive_element: 3
In [11]: GF = galois.GF(2**100); print(GF.properties)
GF(2^100):
characteristic: 2
degree: 100
order: 1267650600228229401496703205376
irreducible_poly: x^100 + x^57 + x^56 + x^55 + x^52 + x^48 + x^47 + x^46 + x^45 + x^44 + x^43 + x^41 + x^37 + x^36 + x^35 + x^34 + x^31 + x^30 + x^27 + x^25 + x^24 + x^22 + x^20 + x^19 + x^16 + x^15 + x^11 + x^9 + x^8 + x^6 + x^5 + x^3 + 1
is_primitive_poly: True
primitive_element: x
Array creation
Galois field arrays can be created from existing NumPy arrays.
# Represents an existing numpy array
In [12]: array = np.random.randint(0, GF256.order, 10, dtype=int); array
Out[12]: array([ 42, 73, 216, 124, 76, 3, 51, 66, 190, 124])
# Explicit Galois field array creation -- a copy is performed
In [13]: GF256(array)
Out[13]: GF([ 42, 73, 216, 124, 76, 3, 51, 66, 190, 124], order=2^8)
# Or view an existing numpy array as a Galois field array -- no copy is performed
In [14]: array.view(GF256)
Out[14]: GF([ 42, 73, 216, 124, 76, 3, 51, 66, 190, 124], order=2^8)
Or they can be created from “array-like” objects. These include strings representing a Galois field element as a polynomial over its prime subfield.
# Arrays can be specified as iterables of iterables
In [15]: GF256([[217, 130, 42], [74, 208, 113]])
Out[15]:
GF([[217, 130, 42],
[ 74, 208, 113]], order=2^8)
# You can mix-and-match polynomial strings and integers
In [16]: GF256(["x^6 + 1", 2, "1", "x^5 + x^4 + x"])
Out[16]: GF([65, 2, 1, 50], order=2^8)
# Single field elements are 0-dimensional arrays
In [17]: GF256("x^6 + x^4 + 1")
Out[17]: GF(81, order=2^8)
Galois field arrays also have constructor class methods for convenience. They include:
galois.FieldArray.Zeros()
,galois.FieldArray.Ones()
,galois.FieldArray.Identity()
,galois.FieldArray.Range()
,galois.FieldArray.Random()
,galois.FieldArray.Elements()
Galois field elements can either be displayed using their integer representation, polynomial representation, or
power representation. Calling galois.FieldClass.display()
will change the element representation. If called as a context
manager, the display mode will only be temporarily changed.
In [18]: a = GF256(["x^6 + 1", 0, 2, "1", "x^5 + x^4 + x"]); a
Out[18]: GF([65, 0, 2, 1, 50], order=2^8)
# Set the display mode to represent GF(2^8) field elements as polynomials over GF(2) with degree less than 8
In [19]: GF256.display("poly");
In [20]: a
Out[20]: GF([α^6 + 1, 0, α, 1, α^5 + α^4 + α], order=2^8)
# Temporarily set the display mode to represent GF(2^8) field elements as powers of the primitive element
In [21]: with GF256.display("power"):
....: print(a)
....:
GF([α^191, 0, α, 1, α^194], order=2^8)
# Resets the display mode to the integer representation
In [22]: GF256.display();
Field arithmetic
Galois field arrays are treated like any other NumPy array. Array arithmetic is performed using Python operators or NumPy functions.
In the list below, GF
is a Galois field array class created by GF = galois.GF(p**m)
, x
and y
are GF
arrays, and z
is an
integer numpy.ndarray
. All arithmetic operations follow normal NumPy broadcasting rules.
Addition:
x + y == np.add(x, y)
Subtraction:
x - y == np.subtract(x, y)
Multiplication:
x * y == np.multiply(x, y)
Division:
x / y == x // y == np.divide(x, y)
Scalar multiplication:
x * z == np.multiply(x, z)
, e.g.x * 3 == x + x + x
Additive inverse:
-x == np.negative(x)
Multiplicative inverse:
GF(1) / x == np.reciprocal(x)
Exponentiation:
x ** z == np.power(x, z)
, e.g.x ** 3 == x * x * x
Logarithm:
np.log(x)
, e.g.GF.primitive_element ** np.log(x) == x
COMING SOON: Logarithm base
b
:GF.log(x, b)
, whereb
is any field elementSquare root:
r = np.sqrt(x)
, e.g.r ** 2 == (-r) ** 2 == x
Matrix multiplication:
A @ B == np.matmul(A, B)
In [23]: x = GF256.Random((2,5)); x
Out[23]:
GF([[ 88, 34, 240, 130, 61],
[177, 132, 140, 183, 37]], order=2^8)
In [24]: y = GF256.Random(5); y
Out[24]: GF([126, 213, 59, 57, 14], order=2^8)
# y is broadcast over the last dimension of x
In [25]: x + y
Out[25]:
GF([[ 38, 247, 203, 187, 51],
[207, 81, 183, 142, 43]], order=2^8)
Linear algebra
The galois
package intercepts relevant calls to NumPy’s linear algebra functions and performs the specified
operation in \(\mathrm{GF}(p^m)\) not in \(\mathbb{R}\). Some of these functions include:
In [26]: A = GF256.Random((3,3)); A
Out[26]:
GF([[146, 205, 173],
[227, 147, 233],
[114, 0, 118]], order=2^8)
# Ensure A is invertible
In [27]: while np.linalg.matrix_rank(A) < 3:
....: A = GF256.Random((3,3)); A
....:
In [28]: b = GF256.Random(3); b
Out[28]: GF([ 48, 202, 4], order=2^8)
In [29]: x = np.linalg.solve(A, b); x
Out[29]: GF([ 31, 216, 102], order=2^8)
In [30]: np.array_equal(A @ x, b)
Out[30]: True
Galois field arrays also contain matrix decomposition routines and matrix vector spaces not included in NumPy. These include:
NumPy ufunc methods
Galois field arrays support NumPy ufunc methods. This allows the user to apply a ufunc in a unique way across the target
array. The ufunc method signature is <ufunc>.<method>(*args, **kwargs)
. All arithmetic ufuncs are supported. Below
is a list of their ufunc methods.
<method>
:reduce
,accumulate
,reduceat
,outer
,at
In [31]: X = GF256.Random((2,5)); X
Out[31]:
GF([[232, 187, 163, 190, 101],
[136, 229, 167, 60, 14]], order=2^8)
In [32]: np.multiply.reduce(X, axis=0)
Out[32]: GF([ 62, 173, 212, 42, 76], order=2^8)
In [33]: x = GF256.Random(5); x
Out[33]: GF([246, 119, 54, 40, 166], order=2^8)
In [34]: y = GF256.Random(5); y
Out[34]: GF([146, 138, 236, 26, 177], order=2^8)
In [35]: np.multiply.outer(x, y)
Out[35]:
GF([[188, 132, 106, 201, 16],
[200, 116, 145, 82, 23],
[ 41, 195, 248, 134, 253],
[ 83, 180, 255, 183, 66],
[ 26, 241, 137, 186, 148]], order=2^8)
Polynomials over Galois fields
The galois
package supports polynomials over Galois fields with the galois.Poly
class. galois.Poly
does not subclass numpy.ndarray
but instead contains a galois.FieldArray
of coefficients as an attribute
(implements the “has-a”, not “is-a”, architecture).
Polynomials can be created by specifying the polynomial coefficients as either a galois.FieldArray
or an “array-like”
object with the field
keyword argument.
In [36]: p = galois.Poly([172, 22, 0, 0, 225], field=GF256); p
Out[36]: Poly(172x^4 + 22x^3 + 225, GF(2^8))
In [37]: coeffs = GF256([33, 17, 0, 225]); coeffs
Out[37]: GF([ 33, 17, 0, 225], order=2^8)
In [38]: p = galois.Poly(coeffs, order="asc"); p
Out[38]: Poly(225x^3 + 17x + 33, GF(2^8))
Polynomials over Galois fields can also display their coefficients as polynomials over their prime subfields. This can be quite confusing to read, so be warned!
In [39]: print(p)
Poly(225x^3 + 17x + 33, GF(2^8))
In [40]: with GF256.display("poly"):
....: print(p)
....:
Poly((α^7 + α^6 + α^5 + 1)x^3 + (α^4 + 1)x + (α^5 + 1), GF(2^8))
Polynomials can also be created using a number of constructor class methods. They include:
galois.Poly.Zero()
,galois.Poly.One()
,galois.Poly.Identity()
,galois.Poly.Random()
,galois.Poly.Integer()
,galois.Poly.String()
,galois.Poly.Degrees()
,galois.Poly.Roots()
# Construct a polynomial by specifying its roots
In [41]: q = galois.Poly.Roots([155, 37], field=GF256); q
Out[41]: Poly(x^2 + 190x + 71, GF(2^8))
In [42]: q.roots()
Out[42]: GF([ 37, 155], order=2^8)
Polynomial arithmetic is performed using Python operators.
In [43]: p
Out[43]: Poly(225x^3 + 17x + 33, GF(2^8))
In [44]: q
Out[44]: Poly(x^2 + 190x + 71, GF(2^8))
In [45]: p + q
Out[45]: Poly(225x^3 + x^2 + 175x + 102, GF(2^8))
In [46]: divmod(p, q)
Out[46]: (Poly(225x + 57, GF(2^8)), Poly(56x + 104, GF(2^8)))
In [47]: p ** 2
Out[47]: Poly(171x^6 + 28x^2 + 117, GF(2^8))
Polynomials over Galois fields can be evaluated at scalars or arrays of field elements.
In [48]: p = galois.Poly.Degrees([4, 3, 0], [172, 22, 225], field=GF256); p
Out[48]: Poly(172x^4 + 22x^3 + 225, GF(2^8))
# Evaluate the polynomial at a single value
In [49]: p(1)
Out[49]: GF(91, order=2^8)
In [50]: x = GF256.Random((2,5)); x
Out[50]:
GF([[246, 52, 68, 2, 153],
[ 42, 187, 124, 132, 224]], order=2^8)
# Evaluate the polynomial at an array of values
In [51]: p(x)
Out[51]:
GF([[211, 24, 186, 67, 207],
[ 90, 167, 191, 99, 151]], order=2^8)
Polynomials can also be evaluated in superfields. For example, evaluating a Galois field’s irreducible polynomial at one of its elements.
# Notice the irreducible polynomial is over GF(2), not GF(2^8)
In [52]: p = GF256.irreducible_poly; p
Out[52]: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2))
In [53]: GF256.is_primitive_poly
Out[53]: True
# Notice the primitive element is in GF(2^8)
In [54]: alpha = GF256.primitive_element; alpha
Out[54]: GF(2, order=2^8)
# Since p(x) is a primitive polynomial, alpha is one of its roots
In [55]: p(alpha, field=GF256)
Out[55]: GF(0, order=2^8)
Forward error correction codes
To demonstrate the FEC code API, here is an example using BCH codes. Other FEC codes have a similar API.
In [56]: import numpy as np
In [57]: import galois
In [58]: bch = galois.BCH(15, 7); bch
Out[58]: <BCH Code: [15, 7, 5] over GF(2)>
In [59]: bch.generator_poly
Out[59]: Poly(x^8 + x^7 + x^6 + x^4 + 1, GF(2))
# The error-correcting capability
In [60]: bch.t
Out[60]: 2
A message can be either a 1-D vector or a 2-D matrix of messages. Shortened codes are also supported. See the docs for more details.
# Create a matrix of two messages
In [61]: M = galois.GF2.Random((2, bch.k)); M
Out[61]:
GF([[0, 0, 0, 1, 1, 0, 1],
[1, 1, 1, 0, 0, 1, 1]], order=2)
Encoding the message(s) is performed with galois.BCH.encode()
.
In [62]: C = bch.encode(M); C
Out[62]:
GF([[0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0],
[1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0]], order=2)
Decoding the codeword(s) is performed with galois.BCH.decode()
.
# Corrupt the first bit in each codeword
In [63]: C[:,0] ^= 1; C
Out[63]:
GF([[1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0],
[0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0]], order=2)
In [64]: bch.decode(C)
Out[64]:
GF([[0, 0, 0, 1, 1, 0, 1],
[1, 1, 1, 0, 0, 1, 1]], order=2)