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