galois

A performant NumPy extension for Galois fields and their applications

Science Score: 54.0%

This score indicates how likely this project is to be science-related based on various indicators:

✓
CITATION.cff file
Found CITATION.cff file
✓
codemeta.json file
Found codemeta.json file
✓
.zenodo.json file
Found .zenodo.json file
○
DOI references
○
Academic publication links
✓
Committers with academic emails
2 of 15 committers (13.3%) from academic institutions
○
Institutional organization owner
○
JOSS paper metadata
○
Scientific vocabulary similarity
Low similarity (12.4%) to scientific vocabulary

Keywords

aes bch coding-theory cryptography elliptic-curve-cryptography elliptic-curves encryption error-control-coding finite-fields galois galois-fields lfsr ntt number-theory numpy python reed-solomon rsa

Keywords from Contributors

interactive mesh interpretability sequences generic projection optim hacking network-simulation

Last synced: 6 months ago · JSON representation ·

Repository

A performant NumPy extension for Galois fields and their applications

Basic Info

Host: GitHub
Owner: mhostetter
License: mit
Language: Python
Default Branch: main
Homepage: https://mhostetter.github.io/galois/
Size: 140 MB

Statistics

Stars: 420
Watchers: 7
Forks: 37
Open Issues: 47
Releases: 55

Topics

aes bch coding-theory cryptography elliptic-curve-cryptography elliptic-curves encryption error-control-coding finite-fields galois galois-fields lfsr ntt number-theory numpy python reed-solomon rsa

Created over 5 years ago · Last pushed 9 months ago

Metadata Files

Readme License Citation

README.md

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

Warning 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) % p for $\mathrm{GF}(p)$.
Seamless integration with NumPy -- normal NumPy functions work on FieldArrays.
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.

console $ python3 -m pip install galois

Import the galois package in Python.

```python In [1]: import galois

In [2]: galois.version Out[2]: '0.4.6' ```

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)$.

```python In [3]: GF = galois.GF(3**5)

In [4]: print(GF.properties) Galois Field: name: GF(3^5) characteristic: 3 degree: 5 order: 243 irreduciblepoly: x^5 + 2x + 1 isprimitivepoly: True primitiveelement: 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}$.

```python 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.

python 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.

```python 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).

```python

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.

```python

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.

```python 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.

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

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

Owner

Name: Matt Hostetter
Login: mhostetter
Kind: user
Location: Maryland, USA

Repositories: 5
Profile: https://github.com/mhostetter

Wireless/SDR enthusiast

Citation (CITATION.cff)

cff-version: 1.2.0
message: "If you use this software, please cite it as below."
authors:
- family-names: "Hostetter"
  given-names: "Matt"
title: "Galois: A performant NumPy extension for Galois fields"
date-released: 2020-11-15
url: "https://github.com/mhostetter/galois"

GitHub Events

Total

Create event: 10
Release event: 3
Issues event: 39
Watch event: 87
Delete event: 7
Issue comment event: 95
Push event: 53
Pull request review event: 42
Pull request review comment event: 44
Pull request event: 32
Fork event: 9

Last Year

Create event: 10
Release event: 3
Issues event: 39
Watch event: 87
Delete event: 7
Issue comment event: 95
Push event: 53
Pull request review event: 42
Pull request review comment event: 44
Pull request event: 32
Fork event: 9

Committers

Last synced: 9 months ago

All Time

Total Commits: 1,417
Total Committers: 15
Avg Commits per committer: 94.467
Development Distribution Score (DDS): 0.023

Past Year

Commits: 84
Committers: 8
Avg Commits per committer: 10.5
Development Distribution Score (DDS): 0.095

Top Committers

Name	Email	Commits
mhostetter	m**r@g**m	1,385
Iyán Méndez Veiga	i**a@h**h	15
BK-Modding	k**a@g**m	3
Dominik Wernberger	d**r@t**e	2
Frank Yellin	fy@f****m	2
Ivan Stanković	i**c@p**t	1
Konstantin Avadov	k**v@y**m	1
Lasagnenator	3****r	1
Mathieu	m**8@g**m	1
TDQuering	6****g	1
dependabot[bot]	4****]	1
pivizz	p**z@g**m	1
Rafael Haenel	r**l@p**a	1
Justin Charlong	j**g@h**m	1
Semjon Kravtsenko	s**o@c**e	1

Committer Domains (Top 20 + Academic)

cyber.ee: 1 hiddenlevel.com: 1 phas.ubc.ca: 1 posteo.net: 1 fyellin.com: 1 tum.de: 1 hslu.ch: 1

Issues and Pull Requests

Last synced: 6 months ago

All Time

Total issues: 114
Total pull requests: 119
Average time to close issues: 3 months
Average time to close pull requests: about 1 month
Total issue authors: 52
Total pull request authors: 14
Average comments per issue: 2.0
Average comments per pull request: 2.2
Merged pull requests: 97
Bot issues: 0
Bot pull requests: 1

Past Year

Issues: 25
Pull requests: 33
Average time to close issues: 21 days
Average time to close pull requests: 10 days
Issue authors: 20
Pull request authors: 6
Average comments per issue: 1.68
Average comments per pull request: 1.91
Merged pull requests: 22
Bot issues: 0
Bot pull requests: 1

View more stats

Top Authors

Issue Authors

mhostetter (53)
iyanmv (4)
fyellin (4)
davikrehalt (2)
MrVeka (2)
christakahashi (1)
DuckDackRun (1)
sliedes (1)
varun19299 (1)
scarlehoff (1)
jimpo (1)
luckyyang (1)
m3guitar (1)
luan-xiaokun (1)
ktotam1 (1)

Pull Request Authors

mhostetter (102)
fyellin (9)
iyanmv (6)
amirebrahimi (4)
abhishekmittal15 (3)
avadov (2)
TDQuering (2)
Scurrra (2)
semjon00 (2)
rafaelha (2)
dependabot[bot] (2)
MrVeka (1)
jcharlong (1)
pivis (1)
Lasagnenator (1)

Top Labels

Issue Labels

performance (11) poly (10) bug (10) documentation (9) typing (6) feature-request (5) help wanted (4) fec (4) numpy compatibility (3) linear-algebra (2) testing (1) lfsr (1) numba compatibility (1) question (1)

Pull Request Labels

performance (14) documentation (12) poly (10) bug-fix (8) typing (6) linear-algebra (6) numpy compatibility (6) numba compatibility (5) fec (4) new-feature (3) testing (3) bug (2) dependencies (2)

Packages

Total packages: 1
Total downloads:
- pypi 111,642 last-month

Total dependent packages: 6
Total dependent repositories: 15
Total versions: 56
Total maintainers: 1

pypi.org: galois

A performant NumPy extension for Galois fields and their applications

Homepage: https://github.com/mhostetter/galois
Documentation: https://mhostetter.github.io/galois/latest/
License: MIT
Latest release: 0.4.6
published 10 months ago

Versions: 56
Dependent Packages: 6
Dependent Repositories: 15
Downloads: 111,642 Last month

Rankings

Downloads: 1.8%

Dependent packages count: 2.4%

Dependent repos count: 3.7%

Average: 4.1%

Stargazers count: 4.5%

Forks count: 8.2%

Maintainers (1)

mhostetter

Last synced: 6 months ago

Dependencies

.github/workflows/build.yaml actions

actions/checkout v3 composite
actions/setup-python v4 composite
actions/upload-artifact v3 composite

.github/workflows/docs.yaml actions

actions/checkout v3 composite
actions/download-artifact v3 composite
actions/setup-python v4 composite
actions/upload-artifact v3 composite
stefanzweifel/git-auto-commit-action v4 composite

.github/workflows/lint.yaml actions

actions/checkout v3 composite
actions/setup-python v4 composite

.github/workflows/release.yaml actions

actions/checkout v3 composite
actions/create-release v1 composite
actions/download-artifact v3 composite
pypa/gh-action-pypi-publish v1.4.2 composite

.github/workflows/test.yaml actions

actions/checkout v3 composite
actions/setup-python v4 composite
codecov/codecov-action v3 composite
dawidd6/action-download-artifact v2 composite
lewagon/wait-on-check-action v1.0.0 composite
tj-actions/glob v15 composite

docs/requirements.txt pypi

ipykernel *
myst-parser *
sphinx <5.4
sphinx-design *
sphinx-immaterial ==0.11.2
sphinx-last-updated-by-git *

requirements-min.txt pypi

numba ==0.55.0
numpy ==1.21.0
numpy ==1.21.3
typing_extensions ==4.0.0

galois

Science Score: 54.0%

Keywords

Keywords from Contributors

Repository

Basic Info

Statistics

Topics

Metadata Files

README.md

Features

Roadmap

Documentation

Getting Started

Install the package

Create a FieldArray subclass

Create two FieldArray instances

y represents an array created elsewhere in the code

Change the element representation

The default is the integer representation

Reset to the integer representation

Perform array arithmetic

Acknowledgements

Citation

BibTeX

APA

Owner

Citation (CITATION.cff)

GitHub Events

Total

Last Year

Committers

All Time

Past Year

Top Committers

Committer Domains (Top 20 + Academic)

Issues and Pull Requests

All Time

Past Year

Top Authors

Issue Authors

Pull Request Authors

Top Labels

Issue Labels

Pull Request Labels

Packages

pypi.org: galois

Rankings

Maintainers (1)

Dependencies

Create a `FieldArray` subclass

Create two `FieldArray` instances