tessl/pypi-galois

A performant NumPy extension for Galois fields and their applications

—

Pending

Overview

Eval results

Files

Number Theory

Name: tessl/pypi-galois
Author: tessl

Comprehensive number theory functions including prime generation and testing, integer factorization, modular arithmetic, and mathematical utility functions. This module provides the foundation for cryptographic applications and mathematical computation.

Capabilities

Prime Number Generation

Functions for generating prime numbers, including special classes of primes and efficient algorithms for finding primes within specified ranges.

def primes(n):
    """
    Generate all prime numbers ≤ n using sieve methods.
    
    Parameters:
    - n (int): Upper bound for prime generation
    
    Returns:
    np.ndarray: Array of all primes ≤ n
    """

def kth_prime(k):
    """
    Return the k-th prime number (1-indexed).
    
    Parameters:
    - k (int): Prime index (k=1 returns 2, k=2 returns 3, etc.)
    
    Returns:
    int: The k-th prime number
    """

def prev_prime(n):
    """
    Find the largest prime ≤ n.
    
    Parameters:
    - n (int): Upper bound
    
    Returns:
    int: Largest prime ≤ n, or None if no such prime exists
    """

def next_prime(n):
    """
    Find the smallest prime > n.
    
    Parameters:
    - n (int): Lower bound
    
    Returns:
    int: Smallest prime > n
    """

def random_prime(bits, seed=None):
    """
    Generate random prime with specified bit length.
    
    Parameters:
    - bits (int): Bit length of desired prime
    - seed (int, optional): Random seed for reproducibility
    
    Returns:
    int: Random prime with specified bit length
    """

def mersenne_exponents(n=None):
    """
    Return known Mersenne prime exponents.
    
    Parameters:
    - n (int, optional): Maximum exponent, returns all known if None
    
    Returns:
    list: Known Mersenne prime exponents p where 2^p - 1 is prime
    """

def mersenne_primes(n=None):
    """
    Return known Mersenne primes.
    
    Parameters:
    - n (int, optional): Maximum exponent, returns all known if None
    
    Returns:
    list: Known Mersenne primes 2^p - 1
    """

Primality Testing

Probabilistic and deterministic algorithms for testing whether numbers are prime, composite, or have special properties.

def is_prime(n, rounds=None):
    """
    Test if integer is prime using multiple algorithms.
    
    Combines deterministic tests for small numbers with probabilistic
    Miller-Rabin test for larger numbers.
    
    Parameters:
    - n (int): Integer to test
    - rounds (int, optional): Number of Miller-Rabin rounds for probabilistic test
    
    Returns:
    bool: True if n is prime, False otherwise
    """

def is_composite(n):
    """
    Test if integer is composite (not prime and > 1).
    
    Parameters:
    - n (int): Integer to test
    
    Returns:
    bool: True if n is composite, False otherwise
    """

def fermat_primality_test(n, a, rounds=1):
    """
    Fermat primality test with base a.
    
    Tests if a^(n-1) ≡ 1 (mod n). If False, n is definitely composite.
    If True, n is probably prime.
    
    Parameters:
    - n (int): Integer to test
    - a (int): Test base, must be coprime to n
    - rounds (int): Number of test rounds, default 1
    
    Returns:
    bool: True if n passes Fermat test, False if definitely composite
    """

def miller_rabin_primality_test(n, a=None, rounds=None):
    """
    Miller-Rabin probabilistic primality test.
    
    More reliable than Fermat test, can detect Carmichael numbers.
    
    Parameters:
    - n (int): Integer to test  
    - a (int, optional): Test base, random if None
    - rounds (int, optional): Number of test rounds, auto-selected if None
    
    Returns:
    bool: True if n is probably prime, False if definitely composite
    """

def is_prime_power(n):
    """
    Test if n = p^k for some prime p and integer k ≥ 1.
    
    Parameters:
    - n (int): Integer to test
    
    Returns:
    bool or tuple: False if not prime power, (p, k) if n = p^k
    """

def is_perfect_power(n):
    """
    Test if n = c^e for integers c, e with e > 1.
    
    Parameters:
    - n (int): Integer to test
    
    Returns:
    bool or tuple: False if not perfect power, (c, e) if n = c^e
    """

def is_smooth(n, B):
    """
    Test if n is B-smooth (all prime factors ≤ B).
    
    Parameters:
    - n (int): Integer to test
    - B (int): Smoothness bound
    
    Returns:
    bool: True if all prime factors of n are ≤ B
    """

def is_powersmooth(n, B):
    """
    Test if n is B-powersmooth (all prime powers in factorization ≤ B).
    
    Parameters:
    - n (int): Integer to test  
    - B (int): Powersmooth bound
    
    Returns:
    bool: True if all prime powers dividing n are ≤ B
    """

Modular Arithmetic

Functions for modular arithmetic operations, including totient functions, primitive roots, and multiplicative group analysis.

def totatives(n):
    """
    Find all totatives of n (integers 1 ≤ k < n where gcd(k, n) = 1).
    
    Parameters:
    - n (int): Modulus
    
    Returns:
    np.ndarray: Array of totatives of n
    """

def euler_phi(n):
    """
    Euler's totient function φ(n) - count of totatives of n.
    
    Parameters:
    - n (int): Input integer
    
    Returns:
    int: Number of integers 1 ≤ k ≤ n where gcd(k, n) = 1
    """

def carmichael_lambda(n):
    """
    Carmichael lambda function λ(n) - exponent of multiplicative group Z*_n.
    
    Parameters:
    - n (int): Input integer
    
    Returns:
    int: λ(n), the exponent of the multiplicative group modulo n
    """

def is_cyclic(n):
    """
    Test if multiplicative group Z*_n is cyclic.
    
    Parameters:
    - n (int): Modulus
    
    Returns:
    bool: True if Z*_n is cyclic (has primitive roots)
    """

def primitive_root(n, start=1, stop=None, method="min"):
    """
    Find primitive root modulo n (generator of Z*_n).
    
    Parameters:
    - n (int): Modulus (must have primitive roots)
    - start (int): Start search from this value, default 1
    - stop (int, optional): Stop search at this value, defaults to n
    - method (str): Search method - "min", "max", or "random", default "min"
    
    Returns:
    int: A primitive root modulo n
    
    Raises:
    ValueError: If n has no primitive roots
    """

def primitive_roots(n, start=1, stop=None, reverse=False):
    """
    Iterator through all primitive roots modulo n.
    
    Parameters:
    - n (int): Modulus (must have primitive roots)
    - start (int): Start iteration from this value, default 1
    - stop (int, optional): Stop iteration at this value, defaults to n
    - reverse (bool): Iterate in reverse order, default False
    
    Yields:
    int: Primitive roots modulo n
    """

def is_primitive_root(g, n):
    """
    Test if g is a primitive root modulo n.
    
    Parameters:
    - g (int): Candidate primitive root
    - n (int): Modulus
    
    Returns:
    bool: True if g is a primitive root modulo n
    """

Number-Theoretic Symbols

Functions for computing Legendre, Jacobi, and Kronecker symbols used in quadratic residue theory and cryptography.

def legendre_symbol(a, p):
    """
    Compute Legendre symbol (a/p).
    
    The Legendre symbol indicates whether a is a quadratic residue modulo p.
    
    Parameters:
    - a (int): Numerator
    - p (int): Denominator (must be odd prime)
    
    Returns:
    int: -1, 0, or 1
      - 1 if a is quadratic residue mod p
      - -1 if a is quadratic non-residue mod p  
      - 0 if a ≡ 0 (mod p)
    """

def jacobi_symbol(a, n):
    """
    Compute Jacobi symbol (a/n).
    
    Generalization of Legendre symbol to composite moduli.
    
    Parameters:
    - a (int): Numerator
    - n (int): Denominator (must be positive odd)
    
    Returns:
    int: -1, 0, or 1
    """

def kronecker_symbol(a, n):
    """
    Compute Kronecker symbol (a/n).
    
    Further generalization of Jacobi symbol to all integer moduli.
    
    Parameters:
    - a (int): Numerator
    - n (int): Denominator
    
    Returns:
    int: -1, 0, or 1
    """

Integer Factorization

Algorithms for factoring integers and analyzing their divisor structure.

def perfect_power(n):
    """
    Find perfect power decomposition n = c^e with maximal e > 1.
    
    Parameters:
    - n (int): Integer to decompose
    
    Returns:
    tuple or None: (c, e) if n = c^e with e > 1, None otherwise
    """

def trial_division(n, B=None):
    """
    Factor n using trial division up to bound B.
    
    Parameters:
    - n (int): Integer to factor
    - B (int, optional): Trial division bound, defaults to sqrt(n)
    
    Returns:
    tuple: (factors, remainder) where factors are found prime factors
    """

def pollard_p1(n, B=None, B2=None):
    """
    Pollard p-1 factorization algorithm.
    
    Effective when n has prime factor p where p-1 is smooth.
    
    Parameters:
    - n (int): Integer to factor
    - B (int, optional): Stage 1 bound
    - B2 (int, optional): Stage 2 bound
    
    Returns:
    int or None: Non-trivial factor of n, or None if unsuccessful
    """

def pollard_rho(n, c=1):
    """
    Pollard rho factorization algorithm.
    
    Probabilistic algorithm effective for finding small to medium factors.
    
    Parameters:
    - n (int): Integer to factor
    - c (int): Parameter for iteration function, default 1
    
    Returns:
    int or None: Non-trivial factor of n, or None if unsuccessful
    """

def divisors(n):
    """
    Find all positive divisors of n.
    
    Parameters:
    - n (int): Integer to find divisors of
    
    Returns:
    list: All positive divisors of n in ascending order
    """

def divisor_sigma(n, k=1):
    """
    Compute sum of k-th powers of divisors: σ_k(n) = Σ d^k.
    
    Parameters:
    - n (int): Integer
    - k (int): Power, default 1
    
    Returns:
    int: σ_k(n) = sum of d^k over all divisors d of n
    """

Polymorphic Mathematical Functions

Generic mathematical functions that work with both integers and polynomials over finite fields.

def gcd(*args):
    """
    Greatest common divisor of integers or polynomials.
    
    Parameters:
    - *args: Integers or polynomials (must be same type)
    
    Returns:
    int or Poly: GCD of all arguments
    """

def egcd(a, b):
    """
    Extended Euclidean algorithm: find gcd(a,b) and Bézout coefficients.
    
    Parameters:
    - a, b: Integers or polynomials (same type)
    
    Returns:
    tuple: (gcd, x, y) where gcd = x*a + y*b
    """

def lcm(*args):
    """
    Least common multiple of integers or polynomials.
    
    Parameters:
    - *args: Integers or polynomials (must be same type)
    
    Returns:
    int or Poly: LCM of all arguments
    """

def prod(args):
    """
    Product of sequence of integers or polynomials.
    
    Parameters:
    - args: Iterable of integers or polynomials
    
    Returns:
    int or Poly: Product of all elements
    """

def are_coprime(*args):
    """
    Test if arguments are pairwise coprime.
    
    Parameters:
    - *args: Integers or polynomials (must be same type)
    
    Returns:
    bool: True if gcd of any pair equals 1
    """

def crt(remainders, moduli):
    """
    Chinese Remainder Theorem solver.
    
    Find x such that x ≡ remainders[i] (mod moduli[i]) for all i.
    
    Parameters:
    - remainders: Sequence of remainders
    - moduli: Sequence of pairwise coprime moduli
    
    Returns:
    int: Solution x in range [0, product(moduli))
    """

def factors(n):
    """
    Prime factorization of integer or irreducible factorization of polynomial.
    
    Parameters:
    - n: Integer or polynomial
    
    Returns:
    dict: Factorization as {factor: multiplicity, ...}
    """

def is_square_free(n):
    """
    Test if integer/polynomial is square-free (no repeated prime factors).
    
    Parameters:
    - n: Integer or polynomial
    
    Returns:
    bool: True if square-free
    """

Integer Mathematics

Basic integer mathematical functions for roots, logarithms, and special computations.

def isqrt(n):
    """
    Integer square root: largest integer k such that k² ≤ n.
    
    Parameters:
    - n (int): Non-negative integer
    
    Returns:
    int: floor(sqrt(n))
    """

def iroot(n, k):
    """
    Integer k-th root: largest integer r such that r^k ≤ n.
    
    Parameters:
    - n (int): Non-negative integer
    - k (int): Root degree (positive integer)
    
    Returns:
    int: floor(n^(1/k))
    """

def ilog(n, base):
    """
    Integer logarithm: largest integer k such that base^k ≤ n.
    
    Parameters:
    - n (int): Positive integer
    - base (int): Logarithm base (> 1)
    
    Returns:
    int: floor(log_base(n))
    """

Usage Examples

Prime Generation and Testing

import galois

# Generate all primes up to 100
prime_list = galois.primes(100)
print(f"Primes ≤ 100: {prime_list}")

# Get specific primes
print(f"10th prime: {galois.kth_prime(10)}")
print(f"Previous prime ≤ 50: {galois.prev_prime(50)}")
print(f"Next prime > 50: {galois.next_prime(50)}")

# Generate random prime
random_prime = galois.random_prime(bits=256)
print(f"256-bit random prime: {random_prime}")

# Test primality
candidates = [97, 98, 99, 101]
for n in candidates:
    print(f"{n} is prime: {galois.is_prime(n)}")

# Mersenne primes
mersenne_exp = galois.mersenne_exponents(100)
print(f"Mersenne exponents ≤ 100: {mersenne_exp}")

Modular Arithmetic

import galois

# Euler's totient function
n = 12
phi_n = galois.euler_phi(n)
totatives_n = galois.totatives(n)
print(f"φ({n}) = {phi_n}")
print(f"Totatives of {n}: {totatives_n}")

# Primitive roots
p = 17  # Prime with primitive roots
print(f"Is Z*_{p} cyclic: {galois.is_cyclic(p)}")

prim_root = galois.primitive_root(p)
print(f"Primitive root mod {p}: {prim_root}")

all_prim_roots = list(galois.primitive_roots(p))
print(f"All primitive roots mod {p}: {all_prim_roots}")

# Test specific element
g = 3
is_prim = galois.is_primitive_root(g, p)
print(f"{g} is primitive root mod {p}: {is_prim}")

Factorization

import galois

# Factor integers
n = 1024
factors_dict = galois.factors(n)
print(f"Prime factorization of {n}: {factors_dict}")

# Trial division
n = 12345
factors, remainder = galois.trial_division(n, B=100)
print(f"Trial division of {n}: factors={factors}, remainder={remainder}")

# Pollard methods for larger numbers
n = 8051  # 83 * 97
factor = galois.pollard_rho(n)
print(f"Pollard rho found factor of {n}: {factor}")

# Divisors
n = 60
all_divisors = galois.divisors(n)
sigma_1 = galois.divisor_sigma(n, 1)  # Sum of divisors
print(f"Divisors of {n}: {all_divisors}")
print(f"Sum of divisors σ₁({n}): {sigma_1}")

Number-Theoretic Symbols

import galois

# Legendre symbol
a, p = 7, 11
legendre = galois.legendre_symbol(a, p)
print(f"Legendre symbol ({a}/{p}): {legendre}")

# Jacobi symbol  
a, n = 7, 15
jacobi = galois.jacobi_symbol(a, n)
print(f"Jacobi symbol ({a}/{n}): {jacobi}")

# Test quadratic residues
p = 13
quadratic_residues = []
for a in range(1, p):
    if galois.legendre_symbol(a, p) == 1:
        quadratic_residues.append(a)
print(f"Quadratic residues mod {p}: {quadratic_residues}")

Chinese Remainder Theorem

import galois

# Solve system of congruences
# x ≡ 2 (mod 3)
# x ≡ 3 (mod 5)  
# x ≡ 2 (mod 7)
remainders = [2, 3, 2]
moduli = [3, 5, 7]

solution = galois.crt(remainders, moduli)
print(f"CRT solution: x ≡ {solution} (mod {galois.prod(moduli)})")

# Verify solution
for r, m in zip(remainders, moduli):
    print(f"{solution} ≡ {solution % m} (mod {m}) [expected {r}]")

GCD and Extended Euclidean Algorithm

import galois

# Basic GCD
a, b, c = 48, 18, 24
result = galois.gcd(a, b, c)
print(f"gcd({a}, {b}, {c}) = {result}")

# Extended GCD with Bézout coefficients
a, b = 48, 18
gcd_val, x, y = galois.egcd(a, b)
print(f"gcd({a}, {b}) = {gcd_val}")
print(f"Bézout coefficients: {gcd_val} = {x}×{a} + {y}×{b}")
print(f"Verification: {x*a + y*b} = {gcd_val}")

# LCM
lcm_val = galois.lcm(a, b, c)
print(f"lcm({a}, {b}, {c}) = {lcm_val}")

# Test coprimality
numbers = [9, 16, 25]
coprime = galois.are_coprime(*numbers)
print(f"Are {numbers} pairwise coprime: {coprime}")

Integer Roots and Logarithms

import galois

# Integer square root
n = 15
sqrt_n = galois.isqrt(n)
print(f"isqrt({n}) = {sqrt_n} (since {sqrt_n}² = {sqrt_n**2} ≤ {n} < {(sqrt_n+1)**2})")

# Integer k-th roots
n, k = 100, 3
root_n = galois.iroot(n, k)
print(f"iroot({n}, {k}) = {root_n} (since {root_n}³ = {root_n**k} ≤ {n})")

# Integer logarithms
n, base = 1000, 10
log_n = galois.ilog(n, base)
print(f"ilog({n}, {base}) = {log_n} (since {base}^{log_n} = {base**log_n} ≤ {n})")

Performance and Implementation Notes

Sieve Methods: Efficient prime generation using optimized sieve algorithms
Probabilistic Tests: Miller-Rabin with appropriate round counts for security levels
Optimized Algorithms: Fast modular exponentiation and extended GCD implementations
Memory Efficiency: Lazy evaluation for large prime iterations
Cryptographic Quality: Suitable randomness sources for cryptographic prime generation
Field Integration: Seamless operation with finite field elements where applicable