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. Factors the monic polynomial $$f(x)$$ into a product of square-free polynomials. 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.