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 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), where b is any field element

  • Square 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:

# 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)