galois¶
Arrays¶
- class galois.Array(numpy.ndarray)
An abstract
ndarray
subclass over a Galois field or Galois ring.
- 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 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)\).
Important
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 \(\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, output=
'minimal'
) 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)
Determines if the arguments are pairwise coprime.
- galois.egcd(a, b)
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.lcm(*values)
Computes the least common multiple of the arguments.
- galois.prod(*values)
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, moduli)
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.
Primitive roots¶
-
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)
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.random_prime(bits: int, seed: int | None =
None
) 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_prime_power(n: int) bool
Determines if \(n\) is a prime power \(n = p^k\) for prime \(p\) and \(k \ge 1\).
- galois.is_square_free(value)
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 ofnumpy.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 ofnumpy.printoptions()
.
-
galois.set_printoptions(coeffs: 'desc' | 'asc' =
'desc'
) Modifies the print options for the package. This function is the
galois
equivalent ofnumpy.set_printoptions()
.