crchengrong / galois

A performant NumPy extension for Galois fields and their applications

The galois library is a Python 3 package that extends NumPy arrays to operate over finite fields.

The user creates a Galois field array class using GF = galois.GF(p**m). The Galois field array class GF is a subclass of np.ndarray and its constructor x = GF(array_like) mimics the call signature of np.array(). The Galois field array x is operated on like any other NumPy array except all arithmetic is performed in GF(p^m), not R.

Internally, the finite field arithmetic is implemented by replacing NumPy ufuncs. The new ufuncs are written in pure Python and just-in-time compiled with Numba. The ufuncs can be configured to use either lookup tables (for speed) or explicit calculation (for memory savings).

⚠️ Disclaimer
The algorithms implemented in the NumPy ufuncs are not constant-time, but were instead designed for performance. As such, the library could be vulnerable to a side-channel timing attack. This library is not intended for production security, but instead for research & development, reverse engineering, cryptanalysis, experimentation, and general education.

Features

• Supports all Galois fields GF(p^m), even arbitrarily-large fields!
• Faster than native NumPy! GF(x) * GF(y) is faster than (x * y) % p for GF(p).
• Seamless integration with NumPy -- normal NumPy functions work on Galois field arrays.
• Linear algebra over finite fields using normal np.linalg functions.
• Linear transforms over finite fields, such as the FFT with np.fft.fft() and the NTT with galois.ntt().
• Functions to generate irreducible, primitive, and Conway polynomials.
• Univariate polynomials over finite fields with galois.Poly.
• Forward error correction codes with galois.BCH and galois.ReedSolomon.
• Fibonacci and Galois linear-feedback shift registers over any finite field with galois.FLFSR and galois.GLFSR.
• Various number theoretic functions.
• Integer factorization and accompanying algorithms.
• Prime number generation and primality testing.

Roadmap

• Elliptic curves over finite fields
• Galois ring arrays
• GPU support

Documentation

The documentation for galois is located at https://galois.readthedocs.io/en/latest/.

Getting Started

The Getting Started guide is intended to assist the user in installing the library, creating two example arrays, and performing basic array arithmetic. See Basic Usage for more detailed discussions and examples.

Install the package

The latest version of galois can be installed from PyPI using pip.

$ python3 -m pip install galois

Import the galois package in Python.

In [1]: import galois

In [2]: galois.__version__
Out[2]: '0.0.26'

Create a Galois field array class

Next, create a Galois field array class for the specific finite field you'd like to work in. This is created using the galois.GF() class factory. In this example, we are working in GF(2^8).

In [3]: GF = galois.GF(2**8)

In [4]: GF
Out[4]: <class 'numpy.ndarray over GF(2^8)'>

In [5]: print(GF)
Galois Field:
  name: 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

The Galois field array class GF is a subclass of np.ndarray that performs all arithmetic in the Galois field GF(2^8), not in R.

In [6]: issubclass(GF, np.ndarray)
Out[6]: True

See Galois Field Classes for more details.

Create two Galois field arrays

Next, create a new Galois field array x by passing an array-like object to the Galois field array class GF.

In [7]: x = GF([45, 36, 7, 74, 135]); x
Out[7]: GF([ 45,  36,   7,  74, 135], order=2^8)

Create a second Galois field array y by converting an existing NumPy array (without copying it) by invoking .view(). When finished working in the finite field, view it back as a NumPy array with .view(np.ndarray).

# y represents an array created elsewhere in the code
In [8]: y = np.array([103, 146, 186, 83, 112], dtype=int); y
Out[8]: array([103, 146, 186,  83, 112])

In [9]: y = y.view(GF); y
Out[9]: GF([103, 146, 186,  83, 112], order=2^8)

The Galois field array x is an instance of the Galois field array class GF (and also an instance of np.ndarray).

In [10]: isinstance(x, GF)
Out[10]: True

In [11]: isinstance(x, np.ndarray)
Out[11]: True

See Array Creation for more details.

Change the element representation

The display representation of finite field elements can be set to either the integer ("int"), polynomial ("poly"), or power ("power") representation. The default representation is the integer representation since that is natural when working with integer NumPy arrays.

Set the display mode by passing the display keyword argument to galois.GF() or by calling the galois.FieldArrayClass.display() method. Choose whichever element representation is most convenient for you.

# The default representation is the integer representation
In [12]: x
Out[12]: GF([ 45,  36,   7,  74, 135], order=2^8)

In [13]: GF.display("poly"); x
Out[13]: 
GF([α^5 + α^3 + α^2 + 1,           α^5 + α^2,         α^2 + α + 1,
          α^6 + α^3 + α,   α^7 + α^2 + α + 1], order=2^8)

In [14]: GF.display("power"); x
Out[14]: GF([ α^18, α^225, α^198,  α^37,  α^13], order=2^8)

# Reset to the integer representation
In [15]: GF.display("int");

See Field Element Representation for more details.

Perform array arithmetic

Once you have two Galois field arrays, nearly any arithmetic operation can be performed using normal NumPy arithmetic. The traditional NumPy broadcasting rules apply.

Standard element-wise array arithmetic -- like addition, subtraction, multiplication, and division -- are easily preformed.

In [16]: x + y
Out[16]: GF([ 74, 182, 189,  25, 247], order=2^8)

In [17]: x - y
Out[17]: GF([ 74, 182, 189,  25, 247], order=2^8)

In [18]: x * y
Out[18]: GF([133, 197,   1, 125, 239], order=2^8)

In [19]: x / y
Out[19]: GF([ 99, 101,  21, 177,  97], order=2^8)

More complicated arithmetic, like square root and logarithm base alpha, are also supported.

In [20]: np.sqrt(x)
Out[20]: GF([ 58,  44, 134, 154, 218], order=2^8)

In [21]: np.log(x)
Out[21]: array([ 18, 225, 198,  37,  13])

See Array Arithmetic for more details.

Acknowledgements

The galois library is an extension of, and completely dependent on, NumPy. It also heavily relies on Numba and the LLVM just-in-time compiler for optimizing performance of the finite field arithmetic.

Frank Luebeck's compilation of Conway polynomials and Wolfram's compilation of primitive polynomials are used for efficient polynomial lookup, when possible.

Sage is used extensively for generating test vectors for finite field arithmetic and polynomial arithmetic. SymPy is used to generate some test vectors. Octave is used to generate test vectors for forward error correction codes.

This library would not be possible without all of the other libraries mentioned. Thank you to all their developers!

Citation

If this library was useful to you in your research, please cite us. Following the GitHub citation standards, here is the recommended citation.

BibTeX

@software{Hostetter_Galois_2020,
    title = {{Galois: A performant NumPy extension for Galois fields}},
    author = {Hostetter, Matt},
    month = {11},
    year = {2020},
    url = {https://github.com/mhostetter/galois},
}

APA

Hostetter, M. (2020). Galois: A performant NumPy extension for Galois fields [Computer software]. https://github.com/mhostetter/galois