Polynomials for Finite Fields

IrreduciblePolynomial(F, n) : FldFin, RngIntElt -> RngUPolElt

Given a finite field F and a positive integer n > 1, return a polynomial of degree n that is irreducible over F. If a Conway polynomial or a sparse polynomial is available, then it is returned.

RandomIrreduciblePolynomial(F, n) : FldFin, RngIntElt -> RngUPolElt

Given a finite field F and a positive integer n > 1, return a random irreducible polynomial of degree n that is irreducible over F. The polynomial will be dense in general (that is, a Conway or stored sparse polynomial is not used).

IrreducibleLowTermGF2Polynomial(n) : RngIntElt -> RngUPolElt

Given an integer n in the range 1 ≤n ≤100000, return the irreducible polynomial f of the form xⁿ + g where the degree of g is minimal and g is the first such polynomial in lexicographical order.

This uses a database of low-term irreducible polynomials over GF(2), constructed by Allan Steel in 2004 (thanks are expressed to William Stein for providing machines for some of the computations).

IrreducibleSparseGF2Polynomial(n) : RngIntElt -> RngUPolElt

Given an integer n in the range 4 ≤n ≤12800, return the irreducible polynomial f of the form xⁿ + g where g has 2 non-zero terms if possible and 4 non-zero terms if not; g is the first such polynomial in lexicographical order in either case.

This uses a database of sparse irreducible polynomials over GF(2) constructed by Allan Steel in 1998.

PrimitivePolynomial(F, m) : FldFin, RngIntElt -> RngUPolElt

Given a finite field F and a positive integer m > 1, construct a polynomial f of degree m that is primitive over F. Thus, f is irreducible over F, and it has a primitive root of the degree m extension field of F as a root.

AllIrreduciblePolynomials(F, m) : FldFin, RngIntElt -> { RngUPolElt }

Given a finite field F and a positive integer m > 1, construct the set of all monic polynomials of degree m that are irreducible over F.

ConwayPolynomial(p, n) : RngIntElt, RngIntElt -> RngUPolElt

Given a prime p and an exponent n ≥1, return the Conway polynomial of degree n over GF(p). The Conway polynomial is defined in the introduction. Note that this polynomial is read in from a table containing Conway polynomials for a limited range of p, n only.

ExistsConwayPolynomial(p, n) : RngIntElt, RngIntElt -> BoolElt, RngUPolElt

Given a prime p and an exponent n>1, return true and the Conway polynomial if it is known for the field GF(p), false otherwise.