# FiniteFieldPolynomialPackage GF¶

ffdoms.spad line 271 [edit on github]

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

- clexSmaller?: (SparseUnivariatePolynomial GF, SparseUnivariatePolynomial GF) -> Boolean
`clexSmaller?(f, g)`

compares monic`f`

and`g`

of the same degree in the following order. Error: if`f`

or`g`

is not monic or if`f`

and`g`

have different degrees or if common degree is 0.`f < g`

if the constant term of`f`

is zero and constant term of`g`

is nonzero. If both constant term of`f`

and`g`

are nonzero then`f < g`

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

is less than this number for`g`

. If these values are equal, then`lexSmaller?`

is used as ordering predicate.

- cnlexSmaller?: (SparseUnivariatePolynomial GF, SparseUnivariatePolynomial GF) -> Boolean
`cnlexSmaller?(f, g)`

compares monic`f`

and`g`

of the same degree`n`

in the following order. Error: if`f`

or`g`

is not monic or if`f`

and`g`

have different degrees or if common degree is 0.`f < g`

if the constant term of`f`

is zero and constant term of`g`

is nonzero. If both constant term of`f`

and`g`

are nonzero then`f < g`

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

is less than this number for`g`

. If constant terms are equal then`nlexSmaller?`

is used as ordering predicate.

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

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

- lexSmaller?: (SparseUnivariatePolynomial GF, SparseUnivariatePolynomial GF) -> Boolean
`lexSmaller?(f, g)`

compares monic`f`

and`g`

of the same degree in the following order. Error: if`f`

or`g`

is not monic or if`f`

and`g`

have different degrees or if common degree is 0.`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*.

- 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.`lexSmaller?`

is used as ordering predicate.

- 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.`nlexSmaller?`

is used as ordering predicate.

- 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.`cnlexSmaller?`

is used as ordering predicate. 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.`cnlexSmaller?`

is used as ordering predicate. 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.`clexSmaller?`

is used as ordering predicate.

- nlexSmaller?: (SparseUnivariatePolynomial GF, SparseUnivariatePolynomial GF) -> Boolean
`nlexSmaller?(f, g)`

compares monic`f`

and`g`

of the same degree`n`

in the following order. Error: if`f`

or`g`

is not monic or if`f`

and`g`

have different degrees or if common degree is 0.`f < g`

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

is zero and than that for`g`

is nonzero. Also,`f < g`

if both coefficients are nonzero and*lookup*of the coefficient of`f`

is less than that for`g`

. In case those coefficients are equal, then`lexSmaller?`

is used as ordering predicate.

- 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`

.