galois¶

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 \(\mathrm{GF}(p^m)\).

class galois.GF2(galois.FieldArray)

A FieldArray subclass over \(\mathrm{GF}(2)\).

galois.Field(order: int, ...) → Type[FieldArray]

Alias of GF().

galois.GF(order: int, ...) → Type[FieldArray]

Creates a FieldArray subclass for \(\mathrm{GF}(p^m)\).

Primitive elements¶

galois.is_primitive_element(element: PolyLike, ...) → bool

Determines if \(g\) is a primitive element of the Galois field \(\mathrm{GF}(q^m)\) with degree-\(m\) irreducible polynomial \(f(x)\) over \(\mathrm{GF}(q)\).

galois.primitive_element(irreducible_poly: Poly, ...) → Poly

Finds a primitive element \(g\) of the Galois field \(\mathrm{GF}(q^m)\) with degree-\(m\) irreducible polynomial \(f(x)\) over \(\mathrm{GF}(q)\).

galois.primitive_elements(irreducible_poly: Poly) → List[Poly]

Finds all primitive elements \(g\) of the Galois field \(\mathrm{GF}(q^m)\) with degree-\(m\) irreducible polynomial \(f(x)\) over \(\mathrm{GF}(q)\).

Polynomials¶

class galois.Poly

A univariate polynomial \(f(x)\) over \(\mathrm{GF}(p^m)\).

galois.typing.PolyLike

A Union representing objects that can be coerced into a polynomial.

Irreducible polynomials¶

galois.irreducible_poly(order: int, degree: int, ...) → Poly

Returns a monic irreducible polynomial \(f(x)\) over \(\mathrm{GF}(q)\) with degree \(m\).

galois.irreducible_polys(order: int, degree, ...) → Iterator[Poly]

Iterates through all monic irreducible polynomials \(f(x)\) over \(\mathrm{GF}(q)\) with degree \(m\).

Primitive polynomials¶

galois.conway_poly(characteristic: int, degree: int) → Poly

Returns the Conway polynomial \(C_{p,m}(x)\) over \(\mathrm{GF}(p)\) with degree \(m\).

galois.matlab_primitive_poly(characteristic: int, degree) → Poly

Returns Matlab’s default primitive polynomial \(f(x)\) over \(\mathrm{GF}(p)\) with degree \(m\).

galois.primitive_poly(order: int, degree: int, ...) → Poly

Returns a monic primitive polynomial \(f(x)\) over \(\mathrm{GF}(q)\) with degree \(m\).

galois.primitive_polys(order: int, degree, ...) → Iterator[Poly]

Iterates through all monic primitive polynomials \(f(x)\) over \(\mathrm{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 primitive, narrow-sense binary \(\textrm{BCH}(n, k)\) code.

class galois.ReedSolomon

A general \(\textrm{RS}(n, k)\) code.

galois.bch_valid_codes(n: int, ...) → List[Tuple[int, int, int]]

Returns a list of \((n, k, t)\) tuples of valid primitive binary BCH codes.

galois.generator_to_parity_check_matrix(G: FieldArray) → FieldArray

Converts the generator matrix \(\mathbf{G}\) of a linear \([n, k]\) code into its parity-check matrix \(\mathbf{H}\).

galois.parity_check_to_generator_matrix(H: FieldArray) → FieldArray

Converts the parity-check matrix \(\mathbf{H}\) of a linear \([n, k]\) code into its generator matrix \(\mathbf{G}\).

galois.poly_to_generator_matrix(n: int, ...) → FieldArray

Converts the generator polynomial \(g(x)\) into the generator matrix \(\mathbf{G}\) for an \([n, k]\) cyclic code.

galois.roots_to_parity_check_matrix(n: int, roots) → FieldArray

Converts the generator polynomial roots into the parity-check matrix \(\mathbf{H}\) for an \([n, k]\) cyclic code.

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(a: Poly, b: Poly) → Tuple[Poly, Poly, Poly]

Finds the multiplicands of \(a\) and \(b\) such that \(a s + b t = \mathrm{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\ (\textrm{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.is_cyclic(n: int) → bool

Determines whether the multiplicative group \((\mathbb{Z}/n\mathbb{Z}){^\times}\) is cyclic.

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})\).

galois.legendre_symbol(a: int, p: int) → int

Computes the Legendre symbol \((\frac{a}{p})\).

Primitive roots¶

galois.is_primitive_root(g: int, n: int) → bool

Determines if \(g\) is a primitive root modulo \(n\).

galois.primitive_root(n: int, start: int = 1, ...) → int

Finds a primitive root modulo \(n\) in the range \([\textrm{start}, \textrm{stop})\).

galois.primitive_roots(n: int, start: int = 1, ...) → Iterator[int]

Iterates through all primitive roots modulo \(n\) in the range \([\textrm{start}, \textrm{stop})\).

Integer arithmetic¶

galois.ilog(n: int, b: int) → int

Computes \(x = \lfloor\textrm{log}_b(n)\rfloor\) such that \(b^x \le n < b^{x + 1}\).

galois.iroot(n: int, k: int) → int

Computes \(x = \lfloor n^{\frac{1}{k}} \rfloor\) such that \(x^k \le n < (x + 1)^k\).

galois.isqrt(n: int) → int

Computes \(x = \lfloor\sqrt{n}\rfloor\) such that \(x^2 \le n < (x + 1)^2\).

Factorization¶

Prime factorization¶

galois.factors(value: int) → Tuple[List[int], List[int]]

galois.factors(value: Poly) → Tuple[List[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\).

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 \le 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 \le n\).

galois.mersenne_primes(n: int | None = None) → List[int]

Returns all known Mersenne primes \(p\) for \(p \le 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 \le n\).

galois.primes(n: int) → List[int]

Returns all primes \(p\) for \(p \le n\).

galois.random_prime(bits: int) → int

Returns a random prime \(p\) with \(b\) bits, such that \(2^b \le 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 \ge 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().