Polynomials

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

Polynomial classes

Poly(coeffs[, field, order])

A univariate 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[, reverse])	Iterates through 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[, reverse])	Iterates through 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()	Finds the greatest common divisor of \(a\) and \(b\).
egcd()	Finds the multiplicands of \(a\) and \(b\) such that \(a s + b t = \mathrm{gcd}(a, b)\).
lcm()	Computes the least common multiple of the arguments.
prod()	Computes the product of the arguments.
are_coprime()	Determines if the arguments are pairwise coprime.

Congruences

crt()

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

Factorization

factors()

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

Tests

is_square_free()

Determines if an integer or polynomial is square-free.

---

Last update: May 18, 2022