Extended polynomials in library NTL

Question

There is code is written using NTL library:

int main()
{
      ZZ_p::init(ZZ(5)); // define GF(5)

      ZZ_pX P;
      BuildIrred(P, 4); // generate an irreducible polynomial P
                         // of degree 4 over GF(5)

      ZZ_pE::init(P); // define GF(5^4)

      ZZ_pEX f, g, h;  // declare polynomials over GF(5^4)

      random(f, 3);  // f is a random, monic polynomial of degree 3
      SetCoeff(f, 3);
      cout << f << endl<< endl;
}

The output is:

[[3 1 1 4] [2 1 3 2] [1 0 3 1] [1]]

For example, [1 2 3] is mean 3x² + 2x + 1.
What the form of notation polynomial over GF in this case?

Answer 1

Your question is a little bit difficult to understand. If I understand you right, the question is how to interpret the NTL representation [[3 1 1 4] [2 1 3 2] [1 0 3 1] [1]] of a polynomial over the finite field with 5⁴ elements.

First: The elements in the finite field with 5⁴ elements (called GF(5⁴)) are represented as the polynomials GF(5)[X] mod f, where f is an irreducible polynomial of degree 4.

This means a polynomial over GF(5⁴) is a Polynomial where the coefficients are polynomials in GF(5)[X] mod f.

So [[3 1 1 4] [2 1 3 2] [1 0 3 1] [1]] can be interpreted as

Y³ + (X³ + 3X² + 1)⋅Y² + (2X³ + 3X² + X + 2)⋅Y + (4X³ + X² + X + 3)

Notice: The comment in

random(f, 3);  // f is a random, monic polynomial of degree 3
SetCoeff(f, 3);

is a little bit misleading. random(f,3) sets f to a random polynomial of degree less than 3. SetCoeff(f, 3) sets the coefficient of Y³ to 1 and after that it is a polynomial of degree 3.