galois

A performant numpy extension for Galois fields.

Galois Fields

Galois field class creation

GF(order[, irreducible_poly, …])	Factory function to construct a Galois field array class for \(\mathrm{GF}(p^m)\).
Field(order[, irreducible_poly, …])	Alias of galois.GF().
FieldArray(array[, dtype, copy, order, ndmin])	Creates an array over \(\mathrm{GF}(p^m)\).
FieldClass(name, bases, namespace, **kwargs)	Defines a metaclass for all galois.FieldArray classes.

Pre-made Galois field classes

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

Creates an array over \(\mathrm{GF}(2)\).

Prime field functions

primitive_root(n[, start, stop, reverse])	Finds the smallest primitive root modulo \(n\).
primitive_roots(n[, start, stop, reverse])	Finds all primitive roots modulo \(n\).
is_primitive_root(g, n)	Determines if \(g\) is a primitive root modulo \(n\).

Extension field functions

irreducible_poly(characteristic, degree[, …])	Returns a degree-\(m\) irreducible polynomial \(f(x)\) over \(\mathrm{GF}(p)\).
irreducible_polys(characteristic, degree)	Returns all degree-\(m\) irreducible polynomials \(f(x)\) over \(\mathrm{GF}(p)\).
is_irreducible(poly)	Checks whether the polynomial \(f(x)\) over \(\mathrm{GF}(p)\) is irreducible.
primitive_poly(characteristic, degree[, method])	Returns a degree-\(m\) primitive polynomial \(f(x)\) over \(\mathrm{GF}(p)\).
primitive_polys(characteristic, degree)	Returns all degree-\(m\) primitive polynomials \(f(x)\) over \(\mathrm{GF}(p)\).
is_primitive(poly)	Checks whether the polynomial \(f(x)\) over \(\mathrm{GF}(p)\) is primitive.
conway_poly(p, n)	Returns the degree-\(n\) Conway polynomial \(C_{p,n}\) over \(\mathrm{GF}(p)\).
primitive_element(irreducible_poly[, start, …])	Finds the smallest primitive element \(g(x)\) of the Galois field \(\mathrm{GF}(p^m)\) with degree-\(m\) irreducible polynomial \(f(x)\) over \(\mathrm{GF}(p)\).
primitive_elements(irreducible_poly[, …])	Finds all primitive elements \(g(x)\) of the Galois field \(\mathrm{GF}(p^m)\) with degree-\(m\) irreducible polynomial \(f(x)\) over \(\mathrm{GF}(p)\).
is_primitive_element(element, irreducible_poly)	Determines if \(g(x)\) is a primitive element of the Galois field \(\mathrm{GF}(p^m)\) with degree-\(m\) irreducible polynomial \(f(x)\) over \(\mathrm{GF}(p)\).
minimal_poly(element)	Computes the minimal polynomial \(m_e(x) \in \mathrm{GF}(p)[x]\) of a Galois field element \(e \in \mathrm{GF}(p^m)\).

Galois fields for cryptography

Oakley1()	Returns the Galois field for the first Oakley group from RFC 2409.
Oakley2()	Returns the Galois field for the second Oakley group from RFC 2409.
Oakley3()	Returns the Galois field for the third Oakley group from RFC 2409.
Oakley4()	Returns the Galois field for the fourth Oakley group from RFC 2409.

Polynomials over Galois Fields

Polynomial classes

Poly(coeffs[, field, order])

Create a polynomial \(f(x)\) over \(\mathrm{GF}(p^m)\).

Polynomial functions

poly_gcd(a, b)	Finds the greatest common divisor of two polynomials \(a(x)\) and \(b(x)\) over \(\mathrm{GF}(q)\).
poly_pow(poly, power, modulus)	Efficiently exponentiates a polynomial \(f(x)\) to the power \(k\) reducing by modulo \(g(x)\), \(f(x)^k\ \textrm{mod}\ g(x)\).
poly_factors(poly)	Factors the polynomial \(f(x)\) into a product of \(n\) irreducible factors \(f(x) = g_0(x)^{k_0} g_1(x)^{k_1} \dots g_{n-1}(x)^{k_{n-1}}\) with \(k_0 \le k_1 \le \dots \le k_{n-1}\).

Create specific polynomials

irreducible_poly(characteristic, degree[, …])	Returns a degree-\(m\) irreducible polynomial \(f(x)\) over \(\mathrm{GF}(p)\).
irreducible_polys(characteristic, degree)	Returns all degree-\(m\) irreducible polynomials \(f(x)\) over \(\mathrm{GF}(p)\).
primitive_poly(characteristic, degree[, method])	Returns a degree-\(m\) primitive polynomial \(f(x)\) over \(\mathrm{GF}(p)\).
primitive_polys(characteristic, degree)	Returns all degree-\(m\) primitive polynomials \(f(x)\) over \(\mathrm{GF}(p)\).
conway_poly(p, n)	Returns the degree-\(n\) Conway polynomial \(C_{p,n}\) over \(\mathrm{GF}(p)\).
minimal_poly(element)	Computes the minimal polynomial \(m_e(x) \in \mathrm{GF}(p)[x]\) of a Galois field element \(e \in \mathrm{GF}(p^m)\).

Polynomial tests

is_monic(poly)	Determines whether the polynomial is monic, i.e. having leading coefficient equal to 1.
is_irreducible(poly)	Checks whether the polynomial \(f(x)\) over \(\mathrm{GF}(p)\) is irreducible.
is_primitive(poly)	Checks whether the polynomial \(f(x)\) over \(\mathrm{GF}(p)\) is primitive.

Linear Sequences

berlekamp_massey(sequence)

Finds the minimum-degree polynomial \(c(x)\) that produces the sequence in \(\mathrm{GF}(p^m)\).

Forward Error Correcting Codes

BCH Codes

BCH(n, k[, primitive_poly, …])	Constructs a primitive, narrow-sense binary \(\textrm{BCH}(n, k)\) code.
bch_valid_codes(n[, t_min])	Returns a list of \((n, k, t)\) tuples of valid primitive binary BCH codes.
bch_generator_poly(n, k[, c, …])	Returns the generator polynomial for the primitive binary \(\textrm{BCH}(n, k)\) code.
bch_generator_matrix(n, k[, c, …])	Returns the generator matrix for the primitive binary \(\textrm{BCH}(n, k)\) code.

Modular Arithmetic

gcd(a, b)	Finds the integer multiplicands of \(a\) and \(b\) such that \(a x + b y = \mathrm{gcd}(a, b)\).
lcm(*integers)	Computes the least common multiple of the integer arguments.
crt(a, m)	Solves the simultaneous system of congruences for \(x\).
isqrt(n)	Computes the integer square root of \(n\) such that \(\textrm{isqrt}(n)^2 \le n\).
iroot(n, k)	Finds the integer \(k\)-th root \(x\) of \(n\), such that \(x^k \le n\).
ilog(n, b)	Finds the integer \(\textrm{log}_b(n) = k\), such that \(b^k \le n\).
pow(base, exp, mod)	Efficiently exponentiates an integer \(a^k (\textrm{mod}\ m)\).
is_cyclic(n)	Determines whether the multiplicative group \((\mathbb{Z}/n\mathbb{Z}){^\times}\) is cyclic.
carmichael(n)	Finds the smallest positive integer \(m\) such that \(a^m \equiv 1\ (\textrm{mod}\ n)\) for every integer \(a\) in \(1 \le a < n\) that is coprime to \(n\).
euler_totient(n)	Counts the positive integers (totatives) in \(1 \le k < n\) that are relatively prime to \(n\), i.e. \(\mathrm{gcd}(n, k) = 1\).
totatives(n)	Returns the positive integers (totatives) in \(1 \le k < n\) that are coprime with \(n\), i.e. \(\mathrm{gcd}(n, k) = 1\).

Discrete Logarithms

log_naive(beta, alpha, modulus)

Computes the discrete logarithm \(x = \textrm{log}_{\alpha}(\beta)\ (\textrm{mod}\ m)\).

Primes

Prime numbers

primes(n)	Returns all primes \(p\) for \(p \le n\).
kth_prime(k)	Returns the \(k\)-th prime.
prev_prime(n)	Returns the nearest prime \(p\), such that \(p \le n\).
next_prime(n)	Returns the nearest prime \(p\), such that \(p > n\).
random_prime(bits)	Returns a random prime \(p\) with \(b\) bits, such that \(2^b \le p < 2^{b+1}\).
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\).

Primality tests

is_prime(n)	Determines if \(n\) is prime.
is_prime_fermat(n)	Determines if \(n\) is composite.
is_prime_miller_rabin(n[, a, rounds])	Determines if \(n\) is composite.

Prime factorization

prime_factors(n)	Computes the prime factors of the positive integer \(n\).
is_smooth(n, B)	Determines if the positive integer \(n\) is \(B\)-smooth, i.e. all its prime factors satisfy \(p \le B\).