tessl/pypi-galois

A performant NumPy extension for Galois fields and their applications

—

Pending

Overview

Eval results

Files

Polynomial Operations

Name: tessl/pypi-galois
Author: tessl

Univariate polynomial arithmetic over finite fields, including polynomial creation, arithmetic operations, factorization, and specialized polynomial generation functions for Conway, irreducible, and primitive polynomials.

Capabilities

Polynomial Class

Main polynomial class for univariate polynomials over finite fields with comprehensive arithmetic operations and utility methods.

class Poly:
    """
    A univariate polynomial f(x) over GF(p^m).
    """
    
    def __init__(self, coeffs, field=None, order="desc"):
        """
        Create polynomial from coefficients.
        
        Parameters:
        - coeffs: Polynomial coefficients as array-like
        - field: Galois field class, defaults to GF(2) if None
        - order: Coefficient order - "desc" (default) for descending powers, "asc" for ascending
        """
    
    # Properties
    @property
    def field(self) -> type:
        """The Galois field the polynomial is defined over."""
    
    @property
    def degree(self) -> int:
        """The degree of the polynomial."""
    
    @property
    def coeffs(self) -> FieldArray:
        """The polynomial coefficients in descending order."""
    
    @property
    def nonzero_coeffs(self) -> FieldArray:
        """The non-zero coefficients."""
    
    @property
    def nonzero_degrees(self) -> np.ndarray:
        """The degrees with non-zero coefficients."""
    
    @property
    def integer(self) -> int:
        """Integer representation of the polynomial."""
    
    @property
    def string(self) -> str:
        """String representation of the polynomial."""
    
    # Arithmetic operations
    def __call__(self, at, field=None, elementwise=True):
        """
        Evaluate polynomial at given points.
        
        Parameters:
        - at: Points to evaluate at
        - field: Field for evaluation, uses polynomial's field if None
        - elementwise: Whether to evaluate elementwise
        
        Returns:
        Evaluation results
        """
    
    def derivative(self, k=1):
        """
        Compute k-th derivative of polynomial.
        
        Parameters:
        - k: Derivative order, default 1
        
        Returns:
        Poly: The k-th derivative
        """
    
    def reverse(self):
        """
        Reverse the coefficients of the polynomial.
        
        Returns:
        Poly: Polynomial with reversed coefficients
        """
    
    # Polynomial analysis
    def is_monic(self) -> bool:
        """Test if polynomial is monic (leading coefficient is 1)."""
    
    def is_primitive(self) -> bool:
        """Test if polynomial is primitive."""
    
    def is_irreducible(self) -> bool:
        """Test if polynomial is irreducible."""
    
    def is_square_free(self) -> bool:
        """Test if polynomial is square-free."""
    
    # Class methods for special polynomials
    @classmethod
    def Zero(cls, field=None):
        """
        Create zero polynomial.
        
        Parameters:
        - field: Galois field class
        
        Returns:
        Poly: Zero polynomial
        """
    
    @classmethod
    def One(cls, field=None):
        """
        Create constant polynomial f(x) = 1.
        
        Parameters:
        - field: Galois field class
        
        Returns:
        Poly: Unit polynomial
        """
    
    @classmethod
    def Identity(cls, field=None):
        """
        Create identity polynomial f(x) = x.
        
        Parameters:
        - field: Galois field class
        
        Returns:
        Poly: Identity polynomial
        """
    
    @classmethod
    def Random(cls, degree, field=None):
        """
        Create random polynomial of specified degree.
        
        Parameters:
        - degree: Polynomial degree
        - field: Galois field class
        
        Returns:
        Poly: Random polynomial
        """
    
    @classmethod
    def Int(cls, integer, field=None):
        """
        Create polynomial from integer representation.
        
        Parameters:
        - integer: Integer representation
        - field: Galois field class
        
        Returns:
        Poly: Polynomial from integer
        """
    
    @classmethod
    def Str(cls, string, field=None):
        """
        Create polynomial from string representation.
        
        Parameters:
        - string: String representation
        - field: Galois field class
        
        Returns:
        Poly: Polynomial from string
        """

Conway Polynomials

Generate Conway polynomials for consistent field extensions and compatibility with mathematical software.

def conway_poly(characteristic, degree):
    """
    Return Conway polynomial C_{p,n}(x) over GF(p).
    
    Conway polynomials provide a standard choice of irreducible polynomial
    for each extension field, ensuring compatibility between different
    implementations and mathematical software packages.
    
    Parameters:
    - characteristic (int): The characteristic p of the base field
    - degree (int): The degree n of the polynomial
    
    Returns:
    Poly: The Conway polynomial C_{p,n}(x)
    
    Raises:
    LookupError: If Conway polynomial is not available in database
    """

Irreducible Polynomials

Generate irreducible polynomials over finite fields for creating field extensions.

def irreducible_poly(field, degree, terms=None, method="min"):
    """
    Find irreducible polynomial of specified degree over finite field.
    
    Parameters:
    - field: The finite field class GF(p^m)
    - degree (int): Degree of desired irreducible polynomial
    - terms (int, optional): Number of terms in polynomial. If None, finds any irreducible.
    - method (str): Search method - "min" for minimal, "max" for maximal, "random" for random
    
    Returns:
    Poly: An irreducible polynomial of specified degree
    """

def irreducible_polys(field, degree, terms=None, reverse=False):
    """
    Iterate through all irreducible polynomials over finite field.
    
    Parameters:
    - field: The finite field class GF(p^m)  
    - degree (int): Degree of irreducible polynomials
    - terms (int, optional): Number of terms in polynomial. If None, finds all.
    - reverse (bool): Whether to iterate in reverse order
    
    Yields:
    Poly: Irreducible polynomials of specified degree
    """

Primitive Polynomials

Generate primitive polynomials that produce primitive elements when used as irreducible polynomials.

def primitive_poly(field, degree, terms=None, method="min"):
    """
    Find primitive polynomial of specified degree over finite field.
    
    A primitive polynomial generates the full multiplicative group
    when used as the irreducible polynomial for field extension.
    
    Parameters:
    - field: The finite field class GF(p^m)
    - degree (int): Degree of desired primitive polynomial
    - terms (int, optional): Number of terms in polynomial. If None, finds any primitive.
    - method (str): Search method - "min" for minimal, "max" for maximal, "random" for random
    
    Returns:
    Poly: A primitive polynomial of specified degree
    """

def primitive_polys(field, degree, terms=None, reverse=False):
    """
    Iterate through all primitive polynomials over finite field.
    
    Parameters:
    - field: The finite field class GF(p^m)
    - degree (int): Degree of primitive polynomials  
    - terms (int, optional): Number of terms in polynomial. If None, finds all.
    - reverse (bool): Whether to iterate in reverse order
    
    Yields:
    Poly: Primitive polynomials of specified degree
    """

def matlab_primitive_poly(characteristic, degree):
    """
    Return MATLAB-compatible primitive polynomial.
    
    Returns the same primitive polynomial that MATLAB's gfprimpolyy() function
    would return for the same parameters, ensuring compatibility.
    
    Parameters:
    - characteristic (int): The characteristic of the field
    - degree (int): The degree of the polynomial
    
    Returns:
    Poly: MATLAB-compatible primitive polynomial
    """

Lagrange Interpolation

Construct interpolating polynomials through given points using Lagrange interpolation.

def lagrange_poly(x, y):
    """
    Construct Lagrange interpolating polynomial.
    
    Find polynomial of minimal degree that passes through all given points.
    
    Parameters:
    - x: X-coordinates of interpolation points (field array)
    - y: Y-coordinates of interpolation points (field array)
    
    Returns:
    Poly: Lagrange interpolating polynomial
    
    Note: x and y must have same length and x values must be distinct
    """

Usage Examples

Basic Polynomial Operations

import galois

# Create polynomials over GF(2)
p1 = galois.Poly([1, 0, 1])      # x^2 + 1
p2 = galois.Poly([1, 1])         # x + 1

# Arithmetic operations
p3 = p1 + p2  # Addition
p4 = p1 * p2  # Multiplication
p5 = p1 ** 3  # Exponentiation
q, r = divmod(p1, p2)  # Division with remainder

print(f"({p1}) * ({p2}) = {p4}")
print(f"({p1}) / ({p2}) = {q} remainder {r}")

# Polynomial evaluation
GF = galois.GF(2**4)
x_vals = GF([0, 1, 2, 3])
y_vals = p1(x_vals)
print(f"p1 evaluated at {x_vals} = {y_vals}")

Working with Different Fields

import galois

# Polynomials over GF(3^2)
GF9 = galois.GF(3**2)  
p = galois.Poly([1, 2, 0, 1], field=GF9)  # x^3 + 2x^2 + 1
print(f"Polynomial: {p}")
print(f"Degree: {p.degree}")
print(f"Field: {p.field.name}")

# Properties and analysis
print(f"Is monic: {p.is_monic()}")
print(f"Coefficients: {p.coeffs}")
print(f"Non-zero degrees: {p.nonzero_degrees}")
print(f"Non-zero coefficients: {p.nonzero_coeffs}")

# Derivatives
p_deriv = p.derivative()
p_deriv2 = p.derivative(2)
print(f"First derivative: {p_deriv}")
print(f"Second derivative: {p_deriv2}")

Special Polynomial Generation

import galois

# Conway polynomials for standard field extensions
conway = galois.conway_poly(2, 8)  # Conway polynomial for GF(2^8)
print(f"Conway polynomial C_{{2,8}}: {conway}")

# Irreducible polynomials
GF2 = galois.GF(2)
irreducible = galois.irreducible_poly(GF2, 4)
print(f"Irreducible polynomial: {irreducible}")

# All irreducible polynomials of degree 3
for poly in galois.irreducible_polys(GF2, 3):
    print(f"Irreducible: {poly}")

# Primitive polynomials
primitive = galois.primitive_poly(GF2, 4)  
print(f"Primitive polynomial: {primitive}")

# MATLAB-compatible primitive polynomial
matlab_prim = galois.matlab_primitive_poly(2, 4)
print(f"MATLAB primitive: {matlab_prim}")

Lagrange Interpolation

import galois

GF = galois.GF(7)

# Interpolation points
x = GF([1, 2, 3, 4])
y = GF([2, 5, 1, 6])

# Construct interpolating polynomial
interp_poly = galois.lagrange_poly(x, y)
print(f"Interpolating polynomial: {interp_poly}")

# Verify interpolation
for i in range(len(x)):
    result = interp_poly(x[i])
    print(f"f({x[i]}) = {result} (expected {y[i]})")

Advanced Polynomial Analysis

import galois

GF = galois.GF(2)

# Create polynomials for analysis
polys = [
    galois.Poly([1, 0, 1, 1], field=GF),     # x^3 + x + 1
    galois.Poly([1, 1, 0, 1], field=GF),     # x^3 + x^2 + 1  
    galois.Poly([1, 0, 0, 1], field=GF),     # x^3 + 1
]

for i, p in enumerate(polys):
    print(f"Polynomial {i+1}: {p}")
    print(f"  Is irreducible: {p.is_irreducible()}")
    print(f"  Is primitive: {p.is_primitive()}")
    print(f"  Is square-free: {p.is_square_free()}")
    print(f"  Integer form: {p.integer}")
    print()

Performance Notes

Storage Optimization: Uses sparse representation for polynomials with few non-zero terms
Field Integration: Seamlessly works with all finite field classes created by GF()
Efficient Arithmetic: Optimized polynomial multiplication and division algorithms
Database Lookup: Conway polynomials use precomputed database for fast retrieval
Search Algorithms: Efficient irreducible and primitive polynomial search methods