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.