# 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.