The galois library is a Python 3 package that extends NumPy arrays to operate over finite fields.
The user creates a FieldArray subclass using GF = galois.GF(p**m). GF is a subclass of numpy.ndarray
and its constructor x = GF(array_like) mimics the signature of numpy.array(). The FieldArray x is operated
on like any other NumPy array except all arithmetic is performed in \(\mathrm{GF}(p^m)\), not \(\mathbb{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 \(\mathrm{GF}(p^m)\), even arbitrarily large fields!
Faster than native NumPy!
GF(x) * GF(y)is faster than(x * y) % pfor \(\mathrm{GF}(p)\).Seamless integration with NumPy – normal NumPy functions work on
FieldArrayinstances.Linear algebra over finite fields using normal
numpy.linalgfunctions.Linear transforms over finite fields, such as the FFT with
numpy.fft.fft()and the NTT withntt().Functions to generate irreducible, primitive, and Conway polynomials.
Univariate polynomials over finite fields with
Poly.Forward error correction codes with
BCHandReedSolomon.Fibonacci and Galois linear-feedback shift registers over any finite field with
FLFSRandGLFSR.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
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.
The Cunningham Book’s tables of prime factorizations, \(b^n \pm 1\) for \(b \in \{2, 3, 5, 6, 7, 10, 11, 12\}\), are used to generate factorization lookup tables. These lookup tables speed-up the creation of large finite fields by avoiding the need to factor large integers.
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.
@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},
}
Hostetter, M. (2020). Galois: A performant NumPy extension for Galois fields [Computer software]. https://github.com/mhostetter/galois