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?(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?(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(n)$FFPOLY(GF) generates a monic irreducible univariate polynomial of degree n over the finite field GF.
createNormalPoly(n)$FFPOLY(GF) generates a normal polynomial of degree n over the finite field 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(n)$FFPOLY(GF) generates a normal and primitive polynomial of degree n over the field GF.
createPrimitivePoly(n)$FFPOLY(GF) generates a primitive polynomial of degree n over the finite field 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?(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(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(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(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(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(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?(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?(f) tests whether the polynomial f over a finite field is normal, i.e. its roots are linearly independent over the field.
numberOfIrreduciblePoly(n)$FFPOLY(GF) yields the number of monic irreducible univariate polynomials of degree n over the finite field GF.
numberOfNormalPoly(n)$FFPOLY(GF) yields the number of normal polynomials of degree n over the finite field GF.
numberOfPrimitivePoly(n)$FFPOLY(GF) yields the number of primitive polynomials of degree n over the finite field GF.
primitive?(f) tests whether the polynomial f over a finite field is primitive, i.e. all its roots are primitive.
random(n)$FFPOLY(GF) generates a random monic polynomial of degree n over the finite field GF.
random(m, n)$FFPOLY(GF) generates a random monic polynomial of degree d over the finite field GF, d between m and n.
reducedQPowers(f) generates [x, x^q, x^(q^2), ..., x^(q^(n-1))] reduced modulo f where q = size()$GF and n = degree f.