A performant NumPy extension for Galois fields and their applications

## Project description

The `galois`

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

Enjoying the library? Give us a :star: on GitHub!

The user creates a `FieldArray`

subclass using `GF = galois.GF(p**m)`

.
`GF`

is a subclass of `np.ndarray`

and its constructor `x = GF(array_like)`

mimics the signature of `np.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).

WarningThe 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) % p`

for $\mathrm{GF}(p)$.- Seamless integration with NumPy -- normal NumPy functions work on
`FieldArray`

s. - 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`ntt()`

. - Functions to generate irreducible, primitive, and Conway polynomials.
- Univariate polynomials over finite fields with
`Poly`

. - Forward error correction codes with
`BCH`

and`ReedSolomon`

. - Fibonacci and Galois linear-feedback shift registers over any finite field with
`FLFSR`

and`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://mhostetter.github.io/galois/latest/.

## Getting Started

The Getting Started guide is intended to assist the user with 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.3.8'
```

### Create a `FieldArray`

subclass

Next, create a `FieldArray`

subclass
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 $\mathrm{GF}(3^5)$.

```
In [3]: GF = galois.GF(3**5)
In [4]: print(GF.properties)
Galois Field:
name: GF(3^5)
characteristic: 3
degree: 5
order: 243
irreducible_poly: x^5 + 2x + 1
is_primitive_poly: True
primitive_element: x
```

The `FieldArray`

subclass `GF`

is a subclass of
`np.ndarray`

that performs all arithmetic in the Galois field $\mathrm{GF}(3^5)$, not in $\mathbb{R}$.

```
In [5]: issubclass(GF, galois.FieldArray)
Out[5]: True
In [6]: issubclass(GF, np.ndarray)
Out[6]: True
```

See Array Classes for more details.

### Create two `FieldArray`

instances

Next, create a new `FieldArray`

`x`

by passing an
`ArrayLike`

object to `GF`

's constructor.

```
In [7]: x = GF([236, 87, 38, 112]); x
Out[7]: GF([236, 87, 38, 112], order=3^5)
```

The array `x`

is an instance of `FieldArray`

and also
an instance of `np.ndarray`

.

```
In [8]: isinstance(x, galois.FieldArray)
Out[8]: True
In [9]: isinstance(x, np.ndarray)
Out[9]: True
```

Create a second `FieldArray`

`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 [10]: y = np.array([109, 17, 108, 224]); y
Out[10]: array([109, 17, 108, 224])
In [11]: y = y.view(GF); y
Out[11]: GF([109, 17, 108, 224], order=3^5)
```

See Array Creation for more details.

### Change the element representation

The 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 integers are natural when
working with integer NumPy arrays.

Set the element representation by passing the `repr`

keyword argument to `galois.GF()`

or by calling the `repr()`

classmethod. Choose whichever element representation is most convenient.

```
# The default is the integer representation
In [12]: x
Out[12]: GF([236, 87, 38, 112], order=3^5)
In [13]: GF.repr("poly"); x
Out[13]:
GF([2α^4 + 2α^3 + 2α^2 + 2, α^4 + 2α,
α^3 + α^2 + 2, α^4 + α^3 + α + 1], order=3^5)
In [14]: GF.repr("power"); x
Out[14]: GF([α^204, α^16, α^230, α^34], order=3^5)
# Reset to the integer representation
In [15]: GF.repr("int");
```

See 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 -- addition, subtraction, multiplication, and division -- are easily preformed.

```
In [16]: x + y
Out[16]: GF([ 18, 95, 146, 0], order=3^5)
In [17]: x - y
Out[17]: GF([127, 100, 173, 224], order=3^5)
In [18]: x * y
Out[18]: GF([ 21, 241, 179, 82], order=3^5)
In [19]: x / y
Out[19]: GF([ 67, 47, 192, 2], order=3^5)
```

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

```
In [20]: np.sqrt(x)
Out[20]: GF([ 51, 135, 40, 16], order=3^5)
In [21]: np.log(x)
Out[21]: array([204, 16, 230, 34])
```

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.

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.

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

## Project details

## Release history Release notifications | RSS feed

## Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.