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, *, ...)
galois.Field(characteristic: int, degree, ...)

Alias of GF().

galois.GF(order: int, *, ...)
galois.GF(degree: int, ...)

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

Primitive elements¶

galois.primitive_element(...) 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)$$.

galois.is_primitive_element(...) 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)$$.

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.

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, ...) Iterator[Poly]

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

Primitive polynomials¶

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

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

galois.matlab_primitive_poly(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, ...) 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 general $$\textrm{BCH}(n, k)$$ code over $$\mathrm{GF}(q)$$.

class galois.ReedSolomon

A general $$\textrm{RS}(n, k)$$ code over $$\mathrm{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(...) Poly
galois.berlekamp_massey(output)
galois.berlekamp_massey(output)

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

Transforms¶

galois.intt(X: ArrayLike, ...)

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

galois.ntt(x: ArrayLike, size: = None, ...)

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)

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(moduli: ) int
galois.crt(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 $$(\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})$$.

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 = \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$$. If $$n$$ is not a perfect power, then $$c = n$$ and $$e = 1$$.

galois.pollard_p1(n: int, B: int, B2: = 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: = None) list[int]

Returns all known Mersenne exponents $$e$$ for $$e \le n$$.

galois.mersenne_primes(n: = 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, seed: = 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_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)

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