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 16, 2022