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)

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

crt(remainders, moduli)

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

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

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.


Last update: Apr 03, 2022