galois

Subpackages

typing

A subpackage containing type hints for the galois library.

Class factory functions

Field(order[, irreducible_poly, ...])

Alias of GF().

GF(order[, irreducible_poly, ...])

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

Abstract base classes

Array(x[, dtype, copy, order, ndmin])

A ndarray subclass over a Galois field or Galois ring.

FieldArray(x[, dtype, copy, order, ndmin])

A ndarray subclass over \(\mathrm{GF}(p^m)\).

Classes

BCH(n, k[, primitive_poly, ...])

A primitive, narrow-sense binary \(\textrm{BCH}(n, k)\) code.

FLFSR(feedback_poly[, state])

A Fibonacci linear-feedback shift register (LFSR).

GF2(x[, dtype, copy, order, ndmin])

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

GLFSR(feedback_poly[, state])

A Galois linear-feedback shift register (LFSR).

Poly(coeffs[, field, order])

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

ReedSolomon(n, k[, c, primitive_poly, ...])

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

Functions

are_coprime()

Determines if the arguments are pairwise coprime.

bch_valid_codes(n[, t_min])

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

berlekamp_massey()

Finds the minimal polynomial \(c(x)\) that produces the linear recurrent sequence \(y\).

carmichael_lambda(n)

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

conway_poly(characteristic, degree)

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

crt()

Solves the simultaneous system of congruences for \(x\).

distinct_degree_factorization(poly)

Factors the monic, square-free polynomial \(f(x)\) into a product of polynomials whose irreducible factors all have the same degree.

divisor_sigma(n[, k])

Returns the sum of \(k\)-th powers of the positive divisors of \(n\).

divisors(n)

Computes all positive integer divisors \(d\) of the integer \(n\) such that \(d\ |\ n\).

egcd()

Finds the multiplicands of \(a\) and \(b\) such that \(a s + b t = \mathrm{gcd}(a, b)\).

equal_degree_factorization(poly, degree)

Factors the monic, square-free polynomial \(f(x)\) of degree \(rd\) into a product of \(r\) irreducible factors with degree \(d\).

euler_phi(n)

Counts the positive integers (totatives) in \([1, n)\) that are coprime to \(n\).

factors()

Computes the prime factors of a positive integer or the irreducible factors of a non-constant, monic polynomial.

fermat_primality_test(n[, a, rounds])

Determines if \(n\) is composite using Fermat's primality test.

gcd()

Finds the greatest common divisor of \(a\) and \(b\).

generator_to_parity_check_matrix(G)

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

ilog(n, b)

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

intt(X[, size, modulus, scaled])

Computes the Inverse Number-Theoretic Transform (INTT) of \(X\).

iroot(n, k)

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

irreducible_poly(order, degree[, method])

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

irreducible_polys(order, degree[, reverse])

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

is_composite(n)

Determines if \(n\) is composite.

is_cyclic(n)

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

is_irreducible(poly)

Determines whether the polynomial \(f(x)\) over \(\mathrm{GF}(p^m)\) is irreducible.

is_monic(poly)

Determines whether the polynomial is monic.

is_perfect_power(n)

Determines if \(n\) is a perfect power \(n = c^e\) with \(e > 1\).

is_powersmooth(n, B)

Determines if the integer \(n\) is \(B\)-powersmooth.

is_prime(n)

Determines if \(n\) is prime.

is_prime_power(n)

Determines if \(n\) is a prime power \(n = p^k\) for prime \(p\) and \(k \ge 1\).

is_primitive(poly)

Determines whether the polynomial \(f(x)\) over \(\mathrm{GF}(q)\) is primitive.

is_primitive_element(element, irreducible_poly)

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

is_primitive_root(g, n)

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

is_smooth(n, B)

Determines if the integer \(n\) is \(B\)-smooth.

is_square_free()

Determines if an integer or polynomial is square-free.

isqrt(n)

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

jacobi_symbol(a, n)

Computes the Jacobi symbol \((\frac{a}{n})\).

kronecker_symbol(a, n)

Computes the Kronecker symbol \((\frac{a}{n})\).

kth_prime(k)

Returns the \(k\)-th prime.

lagrange_poly(x, y)

Computes the Lagrange interpolating polynomial \(L(x)\) such that \(L(x_i) = y_i\).

lcm()

Computes the least common multiple of the arguments.

legendre_symbol(a, p)

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

matlab_primitive_poly(characteristic, degree)

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

mersenne_exponents([n])

Returns all known Mersenne exponents \(e\) for \(e \le n\).

mersenne_primes([n])

Returns all known Mersenne primes \(p\) for \(p \le 2^n - 1\).

miller_rabin_primality_test(n[, a, rounds])

Determines if \(n\) is composite using the Miller-Rabin primality test.

next_prime(n)

Returns the nearest prime \(p\), such that \(p > n\).

ntt(x[, size, modulus])

Computes the Number-Theoretic Transform (NTT) of \(x\).

parity_check_to_generator_matrix(H)

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

perfect_power(n)

Returns the integer base \(c\) and exponent \(e\) of \(n = c^e\).

pollard_p1(n, B[, B2])

Attempts to find a non-trivial factor of \(n\) if it has a prime factor \(p\) such that \(p-1\) is \(B\)-smooth.

pollard_rho(n[, c])

Attempts to find a non-trivial factor of \(n\) using cycle detection.

poly_to_generator_matrix(n, generator_poly)

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

prev_prime(n)

Returns the nearest prime \(p\), such that \(p \le n\).

primes(n)

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

primitive_element(irreducible_poly[, method])

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

primitive_elements(irreducible_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)\).

primitive_poly(order, degree[, method])

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

primitive_polys(order, degree[, reverse])

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

primitive_root(n[, start, stop, method])

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

primitive_roots(n[, start, stop, reverse])

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

prod()

Computes the product of the arguments.

random_prime(bits)

Returns a random prime \(p\) with \(b\) bits, such that \(2^b \le p < 2^{b+1}\).

roots_to_parity_check_matrix(n, roots)

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

square_free_factorization(poly)

Factors the monic polynomial \(f(x)\) into a product of square-free polynomials.

totatives(n)

Returns the positive integers (totatives) in \([1, n)\) that are coprime to \(n\).

trial_division(n[, B])

Finds all the prime factors \(p_i^{e_i}\) of \(n\) for \(p_i \le B\).
Last update: May 11, 2022