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 \leq n \leq 100000\), return the irreducible polynomial \(f\) of the form \(x^n + 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 \({\bf F}_{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 \leq n \leq 12800\), return the irreducible polynomial \(f\) of the form \(x^n + 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 \({\bf F}_{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 \geq 1\), return the Conway polynomial of degree \(n\) over \({\bf F}_{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 \({\bf F}_{p}\), false otherwise.