Arrays¶

class galois.Array(numpy.ndarray): An abstract ndarray subclass over a Galois field or Galois ring.

galois.typing.ArrayLike: A Union representing objects that can be coerced into a Galois field array.

galois.typing.DTypeLike: A Union representing objects that can be coerced into a NumPy data type.

galois.typing.ElementLike: A Union representing objects that can be coerced into a Galois field element.

galois.typing.IterableLike: A Union representing iterable objects that can be coerced into a Galois field array.

galois.typing.ShapeLike: A Union representing objects that can be coerced into a NumPy shape tuple.

Galois fields¶

class galois.FieldArray(galois.Array): An abstract ndarray subclass over $GF (p^{m})$ .

class galois.GF2(galois.FieldArray): A FieldArray subclass over $GF (2)$ .

galois.Field(order: int, *, ...) → type[FieldArray]
galois.Field(characteristic: int, degree, ...) → type[FieldArray]: Alias of GF().

galois.GF(order: int, *, ...) → type[FieldArray]
galois.GF(characteristic: int, degree: int, ...) → type[FieldArray]: Creates a FieldArray subclass for $GF (p^{m})$ .

Primitive elements¶

galois.primitive_element(irreducible_poly: Poly, ...) → Poly: Finds a primitive element $g$ of the Galois field $GF (q^{m})$ with degree- $m$ irreducible polynomial $f (x)$ over $GF (q)$ .

galois.primitive_elements(irreducible_poly: Poly) → list[Poly]: Finds all primitive elements $g$ of the Galois field $GF (q^{m})$ with degree- $m$ irreducible polynomial $f (x)$ over $GF (q)$ .

galois.is_primitive_element(element: PolyLike, ...) → bool: Determines if $g$ is a primitive element of the Galois field $GF (q^{m})$ with degree- $m$ irreducible polynomial $f (x)$ over $GF (q)$ .

Polynomials¶

class galois.Poly: A univariate polynomial $f (x)$ over $GF (p^{m})$ .

galois.typing.PolyLike: A Union representing objects that can be coerced into a polynomial.

See also

The Number theory section contains many functions that operate on polynomials.

Irreducible polynomials¶

galois.irreducible_poly(order: int, degree: int, ...) → Poly: Returns a monic irreducible polynomial $f (x)$ over $GF (q)$ with degree $m$ .

galois.irreducible_polys(order: int, degree, ...) → Iterator[Poly]: Iterates through all monic irreducible polynomials $f (x)$ over $GF (q)$ with degree $m$ .

Primitive polynomials¶

galois.conway_poly(characteristic: int, degree: int, ...) → Poly: Returns the Conway polynomial $C_{p, m} (x)$ over $GF (p)$ with degree $m$ .

galois.matlab_primitive_poly(characteristic: int, degree) → Poly: Returns Matlab’s default primitive polynomial $f (x)$ over $GF (p)$ with degree $m$ .

galois.primitive_poly(order: int, degree: int, ...) → Poly: Returns a monic primitive polynomial $f (x)$ over $GF (q)$ with degree $m$ .

galois.primitive_polys(order: int, degree, ...) → Iterator[Poly]: Iterates through all monic primitive polynomials $f (x)$ over $GF (q)$ with degree $m$ .

Interpolating polynomials¶

galois.lagrange_poly(x: Array, y: Array) → Poly: Computes the Lagrange interpolating polynomial $L (x)$ such that $L (x_{i}) = y_{i}$ .

Forward error correction¶

class galois.BCH: A general $BCH (n, k)$ code over $GF (q)$ .

class galois.ReedSolomon: A general $RS (n, k)$ code over $GF (q)$ .

Linear sequences¶

class galois.FLFSR: A Fibonacci linear-feedback shift register (LFSR).

class galois.GLFSR: A Galois linear-feedback shift register (LFSR).

galois.berlekamp_massey(sequence: FieldArray, ...) → Poly
galois.berlekamp_massey(sequence: FieldArray, output) → FLFSR
galois.berlekamp_massey(sequence: FieldArray, output) → GLFSR: Finds the minimal polynomial $c (x)$ that produces the linear recurrent sequence $y$ .

Transforms¶

galois.intt(X: ArrayLike, ...) → FieldArray: Computes the Inverse Number-Theoretic Transform (INTT) of $X$ .

galois.ntt(x: ArrayLike, size: int | None = None, ...) → FieldArray: Computes the Number-Theoretic Transform (NTT) of $x$ .

Number theory¶

Divisibility¶

galois.are_coprime(*values: int) → bool
galois.are_coprime(*values: Poly) → bool: Determines if the arguments are pairwise coprime.

galois.egcd(a: int, b: int) → tuple[int, int, int]
galois.egcd(...) → tuple[galois._polys._poly.Poly, galois._polys._poly.Poly, galois._polys._poly.Poly]: Finds the multiplicands of $a$ and $b$ such that $a s + b t = \gcd (a, b)$ .

galois.euler_phi(n: int) → int: Counts the positive integers (totatives) in $[1, n)$ that are coprime to $n$ .

galois.gcd(a: int, b: int) → int
galois.gcd(a: Poly, b: Poly) → Poly: Finds the greatest common divisor of $a$ and $b$ .

galois.lcm(*values: int) → int
galois.lcm(*values: Poly) → Poly: Computes the least common multiple of the arguments.

galois.prod(*values: int) → int
galois.prod(*values: Poly) → Poly: Computes the product of the arguments.

galois.totatives(n: int) → list[int]: Returns the positive integers (totatives) in $[1, n)$ that are coprime to $n$ .

Congruences¶

galois.carmichael_lambda(n: int) → int: Finds the smallest positive integer $m$ such that $a^{m} \equiv 1 (mod n)$ for every integer $a$ in $[1, n)$ that is coprime to $n$ .

galois.crt(remainders: Sequence[int], moduli: Sequence[int]) → int
galois.crt(remainders: Sequence[Poly], moduli) → Poly: Solves the simultaneous system of congruences for $x$ .

galois.jacobi_symbol(a: int, n: int) → int: Computes the Jacobi symbol $(\frac{a}{n})$ .

galois.kronecker_symbol(a: int, n: int) → int: Computes the Kronecker symbol $(\frac{a}{n})$ . The Kronecker symbol extends the Jacobi symbol for all $n$ .

galois.legendre_symbol(a: int, p: int) → int: Computes the Legendre symbol $(\frac{a}{p})$ .

galois.is_cyclic(n: int) → bool: Determines whether the multiplicative group $(Z / n Z)^{\times}$ is cyclic.

Primitive roots¶

galois.primitive_root(n: int, start: int = 1, ...) → int: Finds a primitive root modulo $n$ in the range $[start, stop)$ .

galois.primitive_roots(n: int, start: int = 1, ...) → Iterator[int]: Iterates through all primitive roots modulo $n$ in the range $[start, stop)$ .

galois.is_primitive_root(g: int, n: int) → bool: Determines if $g$ is a primitive root modulo $n$ .

Integer arithmetic¶

galois.ilog(n: int, b: int) → int: Computes $x = ⌊ {log}_{b} (n) ⌋$ such that $b^{x} \leq n < b^{x + 1}$ .

galois.iroot(n: int, k: int) → int: Computes $x = ⌊ n^{\frac{1}{k}} ⌋$ such that $x^{k} \leq n < (x + 1)^{k}$ .

galois.isqrt(n: int) → int: Computes $x = ⌊ \sqrt{n} ⌋$ such that $x^{2} \leq n < (x + 1)^{2}$ .

Factorization¶

Prime factorization¶

galois.factors(value: int) → tuple[list[int], list[int]]
galois.factors(...) → tuple[list[galois._polys._poly.Poly], list[int]]: Computes the prime factors of a positive integer or the irreducible factors of a non-constant, monic polynomial.

Composite factorization¶

galois.divisor_sigma(n: int, k: int = 1) → int: Returns the sum of $k$ -th powers of the positive divisors of $n$ .

galois.divisors(n: int) → list[int]: Computes all positive integer divisors $d$ of the integer $n$ such that $d ∣ n$ .

Specific factorization algorithms¶

galois.perfect_power(n: int) → tuple[int, int]: Returns the integer base $c$ and exponent $e$ of $n = c^{e}$ . If $n$ is not a perfect power, then $c = n$ and $e = 1$ .

galois.pollard_p1(n: int, B: int, B2: int | None = None) → int: Attempts to find a non-trivial factor of $n$ if it has a prime factor $p$ such that $p - 1$ is $B$ -smooth.

galois.pollard_rho(n: int, c: int = 1) → int: Attempts to find a non-trivial factor of $n$ using cycle detection.

galois.trial_division(n, ...) → tuple[list[int], list[int], int]: Finds all the prime factors $p_{i}^{e_{i}}$ of $n$ for $p_{i} \leq B$ .

Primes¶

Prime number generation¶

galois.kth_prime(k: int) → int: Returns the $k$ -th prime, where $k = {1, 2, 3, 4, \dots}$ for primes $p = {2, 3, 5, 7, \dots}$ .

galois.mersenne_exponents(n: int | None = None) → list[int]: Returns all known Mersenne exponents $e$ for $e \leq n$ .

galois.mersenne_primes(n: int | None = None) → list[int]: Returns all known Mersenne primes $p$ for $p \leq 2^{n} - 1$ .

galois.next_prime(n: int) → int: Returns the nearest prime $p$ , such that $p > n$ .

galois.prev_prime(n: int) → int: Returns the nearest prime $p$ , such that $p \leq n$ .

galois.primes(n: int) → list[int]: Returns all primes $p$ for $p \leq n$ .

galois.random_prime(bits: int, seed: int | None = None) → int: Returns a random prime $p$ with $b$ bits, such that $2^{b} \leq p < 2^{b + 1}$ .

Primality tests¶

galois.is_composite(n: int) → bool: Determines if $n$ is composite.

galois.is_perfect_power(n: int) → bool: Determines if $n$ is a perfect power $n = c^{e}$ with $e > 1$ .

galois.is_powersmooth(n: int, B: int) → bool: Determines if the integer $n$ is $B$ -powersmooth.

galois.is_prime(n: int) → bool: Determines if $n$ is prime.

galois.is_prime_power(n: int) → bool: Determines if $n$ is a prime power $n = p^{k}$ for prime $p$ and $k \geq 1$ .

galois.is_smooth(n: int, B: int) → bool: Determines if the integer $n$ is $B$ -smooth.

galois.is_square_free(value: int) → bool
galois.is_square_free(value: Poly) → bool: Determines if an integer or polynomial is square-free.

Specific primality tests¶

galois.fermat_primality_test(n: int, ...) → bool: Determines if $n$ is composite using Fermat’s primality test.

galois.miller_rabin_primality_test(n: int, a: int = 2, ...) → bool: Determines if $n$ is composite using the Miller-Rabin primality test.

Configuration¶

galois.get_printoptions() → dict[str, Any]: Returns the current print options for the package. This function is the galois equivalent of numpy.get_printoptions().

galois.printoptions(**kwargs) → Generator[None, None, None]: A context manager to temporarily modify the print options for the package. This function is the galois equivalent of numpy.printoptions().

galois.set_printoptions(coeffs: 'desc' | 'asc' = 'desc'): Modifies the print options for the package. This function is the galois equivalent of numpy.set_printoptions().

Last update: Aug 06, 2023