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

API v0.0.9

galois

A performant numpy extension for Galois fields.

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

Indices and tables