[MathJax off]

4 Miscellaneous

4.1 Miscellaneous - helper functions

4.1-1 SplitCoeffsAndMonomials

All methods in this section work for both, univariate and multivariate polynomials. Caution is required with univariate polynomials when the exponents of the variable are reduced w.r.t. F, for example with methods ReduceMonomialsOverField, LeadingTermOverField and LeadingMonomialOverField. For example, when an univariate polynomail is used to create an LFSR, we do not wish to reduce its expoenents.

SplitCoeffsAndMonomials takes a finite field F over which the polynomail poly is defined and returns a with the list of coefficients clist that correspond to the monomials in the second list mlist. That is, for the polynomial \(\sum_{i=0}^{n-1}c_im_i\), the method returns \([[c_{n-1}, \dots, c_0], [m_{n-1},\dots, m_0]]\), with coefficients \(c_i\in F\). The monomials \(m_i\) can contain one or more variables, i.e., the method works for both, univariate and multivariate polynomials. In case \(c_i\notin F\) an error is triggered and the method returns fail. The exponents of the monomials are not reduced w.r.t. F.

ReduceMonomialsOverField takes a polynomial poly or a list of monomials mlist and reduces all the exponents modulo (Size(F)-1) for a given field F. If a constant FFE is a part of the list, it will stay untouched. For \(\mathbb{F}_2\) all the exponents are set to 1.

LeadingTermOverField first reduces exponents in all terms modulo (Size(F)-1) for a given field F (using ReduceMonomialsOverField), then returns the leading term of the remaining polynomial.

LeadingMonomialOverField first reduces exponents in all terms modulo (Size(F)-1) for a given field F, then returns the leading monomial of the remaining polynomial. ### nusa: check the example !!!!

gap> K := GF(2);;  y := X(K, "y");; F := GF(2^2);;
gap> poly := [  Z(2^2)*y^3 + y + Z(2^2)^2,
>               Z(2^2)*y^7 + y + Z(2^2)^2,
>               Z(2^2)*x_0*x_1*x_9 + x_3^7*x_12 + Z(2^2)^2*x_5];;
gap>  for p in poly do  Display(SplitCoeffsAndMonomials(F, p)); od;
[ [ Z(2^2), Z(2)^0, Z(2^2)^2 ], [ y^3, y, Z(2)^0 ] ]
[ [ Z(2^2), Z(2)^0, Z(2^2)^2 ], [ y^7, y, Z(2)^0 ] ]
[ [ Z(2)^0, Z(2^2), Z(2^2)^2 ], [ x_3^7*x_12, x_0*x_1*x_9, x_5 ] ]
gap>  for p in poly do  Display(ReduceMonomialsOverField(F, p)); od;
y+Z(2)^0
Z(2^2)^2*y+Z(2^2)^2
Z(2^2)*x_0*x_1*x_9+x_3*x_12+Z(2^2)^2*x_5
> Display(ReduceMonomialsOverField(F,SplitCoeffsAndMonomials(F, p)[2])); od;
[ Z(2)^0, y, Z(2)^0 ]
[ y, y, Z(2)^0 ]
[ x_3*x_12, x_0*x_1*x_9, x_5 ]
gap>  for p in poly do  Display(LeadingTermOverField(F, p)); od;
y
Z(2^2)^2*y
Z(2^2)*x_0*x_1*x_9
gap>  for p in poly do  Display(LeadingMonomialOverField(F, p)); od;
y
y
x_0*x_1*x_9

4.1-2 DegreeOfPolynomialOverField

DegreeOfPolynomialOverField works for both, univariate and multivariate polynomials. Be cautious with univariate polynomials, (the exponents of the indeterminates are reduced w.r.t. F).

DegreeOfPolynomialOverField calls ReduceMonomialsOverField (4.1-1) and returns the degree of the leading term of the reduced polynomial poly or \(clist \ cdot mlist\)

gap> for p in poly do  Display(DegreeOfPolynomialOverField(F, p)); od;
1
1
3

4.1-3 GeneratorOfField

GeneratorOfField returns the root of the defining polynomial if the root is also a generator, otherwise it returns the first element \(\ni: order(x)=Size(F)-1\).

GeneratorWRTDefiningPolynomial returns the the coefficient vector of the element returned by the GeneratorOfField call w.r.t polynomial basis given by the root of the defining polynomial of the field.

generated by GAPDoc2HTML