0
# Galois
1

2
A performant NumPy extension for Galois fields and their applications. This library provides comprehensive finite field arithmetic that extends NumPy arrays to operate over Galois fields, enabling high-performance mathematical computing for cryptography, error correction codes, and number theory applications.
3

4
## Package Information
5

6
- **Package Name**: galois
7
- **Language**: Python
8
- **Installation**: `pip install galois`
9

10
## Core Imports
11

12
```python
13
import galois
14
```
15

16
Common imports for field operations:
17

18
```python
19
from galois import GF, FieldArray, Poly
20
```
21

22
All functionality is available from the main namespace:
23

24
```python
25
import galois
26

27
# Create field classes
28
GF256 = galois.GF(256)
29
GF2 = galois.GF2
30

31
# Work with polynomials  
32
poly = galois.Poly([1, 0, 1, 1])
33

34
# Use error correction codes
35
rs = galois.ReedSolomon(255, 223)
36
```
37

38
## Basic Usage
39

40
```python
41
import galois
42
import numpy as np
43

44
# Create a Galois field GF(2^8) 
45
GF256 = galois.GF(2**8)
46
print(f"Field: {GF256.name}")
47
print(f"Characteristic: {GF256.characteristic}")
48
print(f"Degree: {GF256.degree}")
49
print(f"Order: {GF256.order}")
50

51
# Create field arrays (similar to NumPy arrays)
52
a = GF256([1, 2, 3, 4])
53
b = GF256([5, 6, 7, 8])
54

55
# Finite field arithmetic
56
c = a + b  # Addition in GF(2^8)
57
d = a * b  # Multiplication in GF(2^8)
58
e = a ** 2  # Exponentiation in GF(2^8)
59

60
print(f"a = {a}")
61
print(f"b = {b}")
62
print(f"a + b = {c}")
63
print(f"a * b = {d}")
64
print(f"a^2 = {e}")
65

66
# Linear algebra over finite fields
67
A = GF256([[1, 2], [3, 4]])
68
x = GF256([1, 2])
69
y = A @ x  # Matrix multiplication in GF(2^8)
70
print(f"Matrix-vector product: {y}")
71

72
# Polynomial operations
73
p1 = galois.Poly([1, 0, 1], field=GF256)  # x^2 + 1
74
p2 = galois.Poly([1, 1], field=GF256)     # x + 1
75
p3 = p1 * p2  # Polynomial multiplication
76
print(f"({p1}) * ({p2}) = {p3}")
77
```
78

79
## Architecture
80

81
The galois library is built on a robust architecture that extends NumPy's capabilities:
82

83
- **Field Arrays**: `FieldArray` subclasses extend `np.ndarray` for finite field arithmetic with just-in-time compiled ufuncs using Numba
84
- **Field Factory**: `GF()` creates field classes dynamically, optimized for specific field characteristics and degrees
85
- **Polynomial System**: `Poly` class provides univariate polynomial operations over any finite field
86
- **Code Integration**: Seamless NumPy integration allows existing linear algebra and FFT functions to work over finite fields
87
- **Performance**: Configurable lookup tables vs explicit calculation trade-offs for speed vs memory optimization
88

89
This design enables the library to serve as both a high-performance computational tool and an educational platform for finite field mathematics, cryptography, and error correction theory.
90

91
## Capabilities
92

93
### Field Arrays and Arithmetic
94

95
Core finite field array classes and factory functions for creating and manipulating Galois field arrays with full NumPy integration and optimized arithmetic operations.
96

97
```python { .api }
98
def GF(order, irreducible_poly=None, primitive_element=None, verify=True, compile=None):
99
    """Factory function for creating Galois field array classes."""
100

101
class FieldArray(np.ndarray):
102
    """Base class for arrays over finite fields."""
103

104
class GF2(FieldArray):
105
    """Optimized implementation for GF(2) binary field."""
106
```
107

108
[Field Arrays](./field-arrays.md)
109

110
### Polynomial Operations
111

112
Univariate polynomial arithmetic over finite fields, including polynomial generation, factorization, and specialized polynomials like Conway, irreducible, and primitive polynomials.
113

114
```python { .api }
115
class Poly:
116
    """Univariate polynomial over finite fields."""
117

118
def irreducible_poly(field, degree, terms=None, method="min"):
119
    """Find irreducible polynomial of given degree."""
120

121
def primitive_poly(field, degree, terms=None, method="min"):
122
    """Find primitive polynomial of given degree."""
123

124
def conway_poly(characteristic, degree):
125
    """Return Conway polynomial for field extension."""
126
```
127

128
[Polynomials](./polynomials.md)
129

130
### Error Correction Codes
131

132
Forward error correction implementations including BCH and Reed-Solomon codes with encoding, decoding, and error correction capabilities.
133

134
```python { .api }
135
class BCH:
136
    """BCH (Bose-Chaudhuri-Hocquenghem) error correction code."""
137

138
class ReedSolomon:
139
    """Reed-Solomon error correction code."""
140
```
141

142
[Error Correction](./error-correction.md)
143

144
### Linear Feedback Shift Registers
145

146
Fibonacci and Galois linear feedback shift register implementations for sequence generation and analysis, including the Berlekamp-Massey algorithm.
147

148
```python { .api }
149
class FLFSR:
150
    """Fibonacci Linear Feedback Shift Register."""
151

152
class GLFSR:
153
    """Galois Linear Feedback Shift Register."""
154

155
def berlekamp_massey(sequence):
156
    """Find minimal polynomial of linear recurrence sequence."""
157
```
158

159
[Linear Feedback Shift Registers](./lfsr.md)
160

161
### Number Theory
162

163
Comprehensive number theory functions including prime generation and testing, integer factorization, modular arithmetic, and mathematical functions.
164

165
```python { .api }
166
def is_prime(n, rounds=None):
167
    """Test if integer is prime using multiple algorithms."""
168

169
def next_prime(n):
170
    """Find next prime greater than n."""
171

172
def primes(n):
173
    """Generate all primes up to n."""
174

175
def factors(n):
176
    """Prime factorization of integer."""
177

178
def gcd(*args):
179
    """Greatest common divisor."""
180

181
def euler_phi(n):
182
    """Euler's totient function."""
183
```
184

185
[Number Theory](./number-theory.md)
186

187
### Number Theoretic Transforms
188

189
Fast convolution algorithms using Number Theoretic Transforms (NTT) for efficient polynomial multiplication and discrete convolution over finite fields.
190

191
```python { .api }
192
def ntt(x, size=None, modulus=None):
193
    """
194
    Compute Number Theoretic Transform (NTT) of input sequence.
195
    
196
    Parameters:
197
    - x (array_like): Input sequence
198
    - size (int, optional): Transform size, defaults to len(x)
199
    - modulus (int, optional): NTT modulus, must be of form k*2^n + 1
200
    
201
    Returns:
202
    numpy.ndarray: NTT of input sequence
203
    """
204

205
def intt(x, size=None, modulus=None):
206
    """
207
    Compute Inverse Number Theoretic Transform (INTT) of input sequence.
208
    
209
    Parameters:
210
    - x (array_like): Input sequence  
211
    - size (int, optional): Transform size, defaults to len(x)
212
    - modulus (int, optional): NTT modulus, must match forward transform
213
    
214
    Returns:
215
    numpy.ndarray: INTT of input sequence
216
    """
217
```
218

219
### Configuration and Types
220

221
Package configuration options and type system for enhanced development experience with proper type hints and aliases.
222

223
```python { .api }
224
def set_printoptions(**kwargs):
225
    """Set global print options for field arrays."""
226

227
def get_printoptions():
228
    """Get current print options."""
229

230
# Type aliases available in galois.typing
231
ElementLike = Union[int, np.integer, FieldArray]
232
ArrayLike = Union[FieldArray, Iterable, int, np.integer]
233
```
234

235
[Configuration and Types](./config-types.md)