or run

npx @tessl/cli init
Log in

Version

Tile

Overview

Evals

Files

docs

config-types.mderror-correction.mdfield-arrays.mdindex.mdlfsr.mdnumber-theory.mdpolynomials.md
tile.json

tessl/pypi-galois

A performant NumPy extension for Galois fields and their applications

Workspace
tessl
Visibility
Public
Created
Last updated
Describes
pypipkg:pypi/galois@0.4.x

To install, run

npx @tessl/cli install tessl/pypi-galois@0.4.0

index.mddocs/

Galois

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.

Package Information

  • Package Name: galois
  • Language: Python
  • Installation: pip install galois

Core Imports

import galois

Common imports for field operations:

from galois import GF, FieldArray, Poly

All functionality is available from the main namespace:

import galois

# Create field classes
GF256 = galois.GF(256)
GF2 = galois.GF2

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

# Use error correction codes
rs = galois.ReedSolomon(255, 223)

Basic Usage

import galois
import numpy as np

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

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

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

print(f"a = {a}")
print(f"b = {b}")
print(f"a + b = {c}")
print(f"a * b = {d}")
print(f"a^2 = {e}")

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

# Polynomial operations
p1 = galois.Poly([1, 0, 1], field=GF256)  # x^2 + 1
p2 = galois.Poly([1, 1], field=GF256)     # x + 1
p3 = p1 * p2  # Polynomial multiplication
print(f"({p1}) * ({p2}) = {p3}")

Architecture

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

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

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.

Capabilities

Field Arrays and Arithmetic

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

def GF(order, irreducible_poly=None, primitive_element=None, verify=True, compile=None):
    """Factory function for creating Galois field array classes."""

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

class GF2(FieldArray):
    """Optimized implementation for GF(2) binary field."""

Field Arrays

Polynomial Operations

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

class Poly:
    """Univariate polynomial over finite fields."""

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

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

def conway_poly(characteristic, degree):
    """Return Conway polynomial for field extension."""

Polynomials

Error Correction Codes

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

class BCH:
    """BCH (Bose-Chaudhuri-Hocquenghem) error correction code."""

class ReedSolomon:
    """Reed-Solomon error correction code."""

Error Correction

Linear Feedback Shift Registers

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

class FLFSR:
    """Fibonacci Linear Feedback Shift Register."""

class GLFSR:
    """Galois Linear Feedback Shift Register."""

def berlekamp_massey(sequence):
    """Find minimal polynomial of linear recurrence sequence."""

Linear Feedback Shift Registers

Number Theory

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

def is_prime(n, rounds=None):
    """Test if integer is prime using multiple algorithms."""

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

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

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

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

def euler_phi(n):
    """Euler's totient function."""

Number Theory

Number Theoretic Transforms

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

def ntt(x, size=None, modulus=None):
    """
    Compute Number Theoretic Transform (NTT) of input sequence.
    
    Parameters:
    - x (array_like): Input sequence
    - size (int, optional): Transform size, defaults to len(x)
    - modulus (int, optional): NTT modulus, must be of form k*2^n + 1
    
    Returns:
    numpy.ndarray: NTT of input sequence
    """

def intt(x, size=None, modulus=None):
    """
    Compute Inverse Number Theoretic Transform (INTT) of input sequence.
    
    Parameters:
    - x (array_like): Input sequence  
    - size (int, optional): Transform size, defaults to len(x)
    - modulus (int, optional): NTT modulus, must match forward transform
    
    Returns:
    numpy.ndarray: INTT of input sequence
    """

Configuration and Types

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

def set_printoptions(**kwargs):
    """Set global print options for field arrays."""

def get_printoptions():
    """Get current print options."""

# Type aliases available in galois.typing
ElementLike = Union[int, np.integer, FieldArray]
ArrayLike = Union[FieldArray, Iterable, int, np.integer]

Configuration and Types