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). Numba also provides the ability to “target” the JIT-compiled ufuncs for CPUs or GPUs.

In addition to normal array arithmetic, galois also supports linear algebra (with numpy.linalg functions) and polynomials over Galois fields (with the galois.Poly class).

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.GFArray (which itself subclasses numpy.ndarray) and have galois.GFMeta as their metaclass.

In [5]: issubclass(GF256, np.ndarray)
Out[5]: True

In [6]: issubclass(GF256, galois.GFArray)
Out[6]: True

In [7]: issubclass(type(GF256), galois.GFMeta)
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.GFMeta.

# Summarizes some properties of the Galois field
In [8]: print(GF256.properties)
GF(2^8):
  structure: Finite Field
  characteristic: 2
  degree: 8
  order: 256
  irreducible_poly: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2))
  is_primitive_poly: True
  primitive_element: GF(2, order=2^8)

# 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):
  structure: Finite Field
  characteristic: 36893488147419103183
  degree: 1
  order: 36893488147419103183
  irreducible_poly: Poly(x + 36893488147419103180, GF(36893488147419103183))
  is_primitive_poly: True
  primitive_element: GF(3, order=36893488147419103183)

In [11]: GF = galois.GF(2**100); print(GF.properties)
GF(2^100):
  structure: Finite Field
  characteristic: 2
  degree: 100
  order: 1267650600228229401496703205376
  irreducible_poly: 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, GF(2))
  is_primitive_poly: True
  primitive_element: GF(2, order=2^100)

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([195, 188, 120, 144, 182, 218, 236, 238,  71, 249])

# Explicit Galois field array creation (a copy is performed)
In [13]: GF256(array)
Out[13]: GF([195, 188, 120, 144, 182, 218, 236, 238,  71, 249], 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([195, 188, 120, 144, 182, 218, 236, 238,  71, 249], 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.GFMeta.display() will change the element representation. If called as a context manager, the display mode will only be temporarily changed.

In [18]: x = GF256(["y**6 + 1", 0, 2, "1", "y**5 + y**4 + y"]); x
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]: x
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(x)
   ....: 
GF([α^191, -∞, α, 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

  • Matrix multiplication: A @ B == np.matmul(A, B)

In [23]: x = GF256.Random((2,5)); x
Out[23]: 
GF([[168, 237,  60, 238,  17],
    [150,  34,  92, 227,  90]], order=2^8)

In [24]: y = GF256.Random(5); y
Out[24]: GF([185, 101,  62, 248,  70], order=2^8)

# y is broadcast over the last dimension of x
In [25]: x + y
Out[25]: 
GF([[ 17, 136,   2,  22,  87],
    [ 47,  71,  98,  27,  28]], 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:

  • np.trace()

  • np.dot(), np.inner(), np.outer()

  • np.linalg.matrix_rank(), np.linalg.matrix_power()

  • np.linalg.det(), np.linalg.inv(), np.linalg.solve()

In [26]: A = GF256.Random((3,3)); A
Out[26]: 
GF([[ 39, 216, 230],
    [  7, 112, 163],
    [212, 114,  15]], order=2^8)

In [27]: b = GF256.Random(3); b
Out[27]: GF([154, 189,  42], order=2^8)

In [28]: x = np.linalg.solve(A, b); x
Out[28]: GF([169, 199, 231], order=2^8)

In [29]: np.array_equal(A @ x, b)
Out[29]: True

Galois field arrays also contain matrix decomposition routines 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 [30]: X = GF256.Random((2,5)); X
Out[30]: 
GF([[205,  46, 246,  48, 238],
    [  2, 184,  15, 133, 201]], order=2^8)

In [31]: np.multiply.reduce(X, axis=0)
Out[31]: GF([135, 128,  27, 213, 194], order=2^8)
In [32]: x = GF256.Random(5); x
Out[32]: GF([200, 200,  64, 241, 235], order=2^8)

In [33]: y = GF256.Random(5); y
Out[33]: GF([ 97, 155, 187,  41,  29], order=2^8)

In [34]: np.multiply.outer(x, y)
Out[34]: 
GF([[128, 183, 143, 254, 221],
    [128, 183, 143, 254, 221],
    [101,   9, 225, 146,  19],
    [ 44,  79,   4,  97,  98],
    [159, 141, 161, 204, 125]], order=2^8)

Numpy functions

Many other relevant numpy functions are supported on Galois field arrays. These include:

Polynomial construction

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.GFArray 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.GFArray or an “array-like” object with the field keyword argument.

In [35]: p = galois.Poly([172, 22, 0, 0, 225], field=GF256); p
Out[35]: Poly(172x^4 + 22x^3 + 225, GF(2^8))

In [36]: coeffs = GF256([33, 17, 0, 225]); coeffs
Out[36]: GF([ 33,  17,   0, 225], order=2^8)

In [37]: p = galois.Poly(coeffs, order="asc"); p
Out[37]: Poly(225x^3 + 17x + 33, GF(2^8))

Polynomials over Galois fields can also display the field elements as polynomials over their prime subfields. This can be quite confusing to read, so be warned!

In [38]: print(p)
Poly(225x^3 + 17x + 33, GF(2^8))

In [39]: 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 [40]: q = galois.Poly.Roots([155, 37], field=GF256); q
Out[40]: Poly(x^2 + 190x + 71, GF(2^8))

In [41]: q.roots()
Out[41]: GF([ 37, 155], order=2^8)

Polynomial arithmetic

Polynomial arithmetic is performed using python operators.

In [42]: p
Out[42]: Poly(225x^3 + 17x + 33, GF(2^8))

In [43]: q
Out[43]: Poly(x^2 + 190x + 71, GF(2^8))

In [44]: p + q
Out[44]: Poly(225x^3 + x^2 + 175x + 102, GF(2^8))

In [45]: divmod(p, q)
Out[45]: (Poly(225x + 57, GF(2^8)), Poly(56x + 104, GF(2^8)))

In [46]: p ** 2
Out[46]: Poly(171x^6 + 28x^2 + 117, GF(2^8))

Polynomials over Galois fields can be evaluated at scalars or arrays of field elements.

In [47]: p = galois.Poly.Degrees([4, 3, 0], [172, 22, 225], field=GF256); p
Out[47]: Poly(172x^4 + 22x^3 + 225, GF(2^8))

# Evaluate the polynomial at a single value
In [48]: p(1)
Out[48]: GF(91, order=2^8)

In [49]: x = GF256.Random((2,5)); x
Out[49]: 
GF([[136, 243,  33,  53,  69],
    [242,  35, 253, 161, 226]], order=2^8)

# Evaluate the polynomial at an array of values
In [50]: p(x)
Out[50]: 
GF([[153, 175,  53, 181,  20],
    [234,  64, 147, 140,  45]], 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 [51]: p = GF256.irreducible_poly; p
Out[51]: Poly(x^8 + x^4 + x^3 + x^2 + 1, GF(2))

In [52]: GF256.is_primitive_poly
Out[52]: True

# Notice the primitive element is in GF(2^8)
In [53]: alpha = GF256.primitive_element; alpha
Out[53]: GF(2, order=2^8)

# Since p(x) is a primitive polynomial, alpha is one of its roots
In [54]: p(alpha, field=GF256)
Out[54]: GF(0, order=2^8)