Polynomials over Galois Fields

This section contains classes and functions for creating polynomials over Galois fields.

Polynomial classes

Poly(coeffs[, field, order])

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

Special polynomials

Irreducible polynomials

irreducible_poly(order, degree[, method])	Returns a monic irreducible polynomial \(f(x)\) over \(\mathrm{GF}(q)\) with degree \(m\).
irreducible_polys(order, degree)	Returns all monic irreducible polynomials \(f(x)\) over \(\mathrm{GF}(q)\) with degree \(m\).

Primitive polynomials

primitive_poly(order, degree[, method])	Returns a monic primitive polynomial \(f(x)\) over \(\mathrm{GF}(q)\) with degree \(m\).
primitive_polys(order, degree)	Returns all monic primitive polynomials \(f(x)\) over \(\mathrm{GF}(q)\) with degree \(m\).
conway_poly(characteristic, degree)	Returns the Conway polynomial \(C_{p,m}(x)\) over \(\mathrm{GF}(p)\) with degree \(m\).
matlab_primitive_poly(characteristic, degree)	Returns Matlab’s default primitive polynomial \(f(x)\) over \(\mathrm{GF}(p)\) with degree \(m\).

Minimal polynomials

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 functions

Divisibility

gcd(a, b)	Finds the greatest common divisor of \(a\) and \(b\).
egcd(a, b)	Finds the multiplicands of \(a\) and \(b\) such that \(a s + b t = \mathrm{gcd}(a, b)\).
lcm(*values)	Computes the least common multiple of the arguments.
prod(*values)	Computes the product of the arguments.
are_coprime(*values)	Determines if the arguments are pairwise coprime.

Congruences

pow(base, exponent, modulus)	Efficiently performs modular exponentiation.
crt(remainders, moduli)	Solves the simultaneous system of congruences for \(x\).

Polynomial factorization

factors(value)	Computes the prime factors of a positive integer or the irreducible factors of a non-constant, monic polynomial.
square_free_factorization(poly)	Factors the monic polynomial \(f(x)\) into a product of square-free polynomials.
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.
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\).

Polynomial tests

is_monic(poly)	Determines whether the polynomial is monic, i.e. having leading coefficient equal to 1.
is_irreducible(poly)	Determines whether the polynomial \(f(x)\) over \(\mathrm{GF}(p^m)\) is irreducible.
is_primitive(poly)	Determines whether the polynomial \(f(x)\) over \(\mathrm{GF}(q)\) is primitive.
is_square_free(value)	Determines if the positive integer or the non-constant, monic polynomial is square-free.