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

Interpolating polynomials

lagrange_poly(x, y)

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

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.
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 an integer or polynomial is square-free.