# FiniteFieldPolynomialPackage GFΒΆ

This package provides a number of functions for generating, counting and testing irreducible, normal, primitive, random polynomials over finite fields.

- createIrreduciblePoly: PositiveInteger -> SparseUnivariatePolynomial GF
`createIrreduciblePoly(n)`

$FFPOLY(`GF`

) generates a monic irreducible univariate polynomial of degree`n`

over the finite field*GF*.

- createNormalPoly: PositiveInteger -> SparseUnivariatePolynomial GF
`createNormalPoly(n)`

$FFPOLY(`GF`

) generates a normal polynomial of degree`n`

over the finite field*GF*.

- createNormalPrimitivePoly: PositiveInteger -> SparseUnivariatePolynomial GF
`createNormalPrimitivePoly(n)`

$FFPOLY(`GF`

) generates a normal and primitive polynomial of degree`n`

over the field*GF*. Note: this function is equivalent to createPrimitiveNormalPoly(`n`

)

- createPrimitiveNormalPoly: PositiveInteger -> SparseUnivariatePolynomial GF
`createPrimitiveNormalPoly(n)`

$FFPOLY(`GF`

) generates a normal and primitive polynomial of degree`n`

over the field*GF*. polynomial of degree`n`

over the field*GF*.

- createPrimitivePoly: PositiveInteger -> SparseUnivariatePolynomial GF
`createPrimitivePoly(n)`

$FFPOLY(`GF`

) generates a primitive polynomial of degree`n`

over the finite field*GF*.

- leastAffineMultiple: SparseUnivariatePolynomial GF -> SparseUnivariatePolynomial GF
`leastAffineMultiple(f)`

computes the least affine polynomial which is divisible by the polynomial`f`

over the finite field*GF*, i.e. a polynomial whose exponents are 0 or a power of`q`

, the size of*GF*.

- nextIrreduciblePoly: SparseUnivariatePolynomial GF -> Union(SparseUnivariatePolynomial GF, failed)
`nextIrreduciblePoly(f)`

yields the next monic irreducible polynomial over a finite field*GF*of the same degree as`f`

in the following order, or “failed” if there are no greater ones. Error: if`f`

has degree 0. Note: the input polynomial`f`

is made monic. Also,`f < g`

if the number of monomials of`f`

is less than this number for`g`

. If`f`

and`g`

have the same number of monomials, the lists of exponents are compared lexicographically. If these lists are also equal, the lists of coefficients are compared according to the lexicographic ordering induced by the ordering of the elements of*GF*given by*lookup*.

- nextNormalPoly: SparseUnivariatePolynomial GF -> Union(SparseUnivariatePolynomial GF, failed)
`nextNormalPoly(f)`

yields the next normal polynomial over a finite field*GF*of the same degree as`f`

in the following order, or “failed” if there are no greater ones. Error: if`f`

has degree 0. Note: the input polynomial`f`

is made monic. Also,`f < g`

if the*lookup*of the coefficient of the term of degree*n-1*of`f`

is less than that for`g`

. In case these numbers are equal,`f < g`

if if the number of monomials of`f`

is less that for`g`

or if the list of exponents of`f`

are lexicographically less than the corresponding list for`g`

. If these lists are also equal, the lists of coefficients are compared according to the lexicographic ordering induced by the ordering of the elements of*GF*given by*lookup*.

- nextNormalPrimitivePoly: SparseUnivariatePolynomial GF -> Union(SparseUnivariatePolynomial GF, failed)
`nextNormalPrimitivePoly(f)`

yields the next normal primitive polynomial over a finite field*GF*of the same degree as`f`

in the following order, or “failed” if there are no greater ones. Error: if`f`

has degree 0. Note: the input polynomial`f`

is made monic. Also,`f < g`

if the*lookup*of the constant term of`f`

is less than this number for`g`

or if*lookup*of the coefficient of the term of degree*n-1*of`f`

is less than this number for`g`

. Otherwise,`f < g`

if the number of monomials of`f`

is less than that for`g`

or if the lists of exponents for`f`

are lexicographically less than those for`g`

. If these lists are also equal, the lists of coefficients are compared according to the lexicographic ordering induced by the ordering of the elements of*GF*given by*lookup*. This operation is equivalent to nextPrimitiveNormalPoly(`f`

).

- nextPrimitiveNormalPoly: SparseUnivariatePolynomial GF -> Union(SparseUnivariatePolynomial GF, failed)
`nextPrimitiveNormalPoly(f)`

yields the next primitive normal polynomial over a finite field*GF*of the same degree as`f`

in the following order, or “failed” if there are no greater ones. Error: if`f`

has degree 0. Note: the input polynomial`f`

is made monic. Also,`f < g`

if the*lookup*of the constant term of`f`

is less than this number for`g`

or, in case these numbers are equal, if the*lookup*of the coefficient of the term of degree*n-1*of`f`

is less than this number for`g`

. If these numbers are equals,`f < g`

if the number of monomials of`f`

is less than that for`g`

, or if the lists of exponents for`f`

are lexicographically less than those for`g`

. If these lists are also equal, the lists of coefficients are coefficients according to the lexicographic ordering induced by the ordering of the elements of*GF*given by*lookup*. This operation is equivalent to nextNormalPrimitivePoly(`f`

).

- nextPrimitivePoly: SparseUnivariatePolynomial GF -> Union(SparseUnivariatePolynomial GF, failed)
`nextPrimitivePoly(f)`

yields the next primitive polynomial over a finite field*GF*of the same degree as`f`

in the following order, or “failed” if there are no greater ones. Error: if`f`

has degree 0. Note: the input polynomial`f`

is made monic. Also,`f < g`

if the*lookup*of the constant term of`f`

is less than this number for`g`

. If these values are equal, then`f < g`

if if the number of monomials of`f`

is less than that for`g`

or if the lists of exponents of`f`

are lexicographically less than the corresponding list for`g`

. If these lists are also equal, the lists of coefficients are compared according to the lexicographic ordering induced by the ordering of the elements of*GF*given by*lookup*.

- normal?: SparseUnivariatePolynomial GF -> Boolean
`normal?(f)`

tests whether the polynomial`f`

over a finite field is normal, i.e. its roots are linearly independent over the field.

- numberOfIrreduciblePoly: PositiveInteger -> PositiveInteger
`numberOfIrreduciblePoly(n)`

$FFPOLY(`GF`

) yields the number of monic irreducible univariate polynomials of degree`n`

over the finite field*GF*.

- numberOfNormalPoly: PositiveInteger -> PositiveInteger
`numberOfNormalPoly(n)`

$FFPOLY(`GF`

) yields the number of normal polynomials of degree`n`

over the finite field*GF*.

- numberOfPrimitivePoly: PositiveInteger -> PositiveInteger
`numberOfPrimitivePoly(n)`

$FFPOLY(`GF`

) yields the number of primitive polynomials of degree`n`

over the finite field*GF*.

- primitive?: SparseUnivariatePolynomial GF -> Boolean
`primitive?(f)`

tests whether the polynomial`f`

over a finite field is primitive, i.e. all its roots are primitive.

- random: (PositiveInteger, PositiveInteger) -> SparseUnivariatePolynomial GF
`random(m, n)`

$FFPOLY(`GF`

) generates a random monic polynomial of degree`d`

over the finite field*GF*,`d`

between`m`

and`n`

.

- random: PositiveInteger -> SparseUnivariatePolynomial GF
`random(n)`

$FFPOLY(`GF`

) generates a random monic polynomial of degree`n`

over the finite field*GF*.

- reducedQPowers: SparseUnivariatePolynomial GF -> PrimitiveArray SparseUnivariatePolynomial GF
`reducedQPowers(f)`

generates`[x, x^q, x^(q^2), ..., x^(q^(n-1))]`

reduced modulo`f`

where`q = size()\$GF`

and`n = degree f`

.