NTL library GF2X

Question

I am experimenting with the Galois Field using the NTL library. GF2 are the integers mod 2, GF2X are polynomials over GF2 and GF2E is the ring/field extension over GF2.

The problem that I am facing is that I initialize the irreducible polynomial as follows

GF2X irreduc;
SetCoeff(irreduc, 128, 1);
SetCoeff(irreduc, 7, 1);
SetCoeff(irreduc, 2, 1);
SetCoeff(irreduc, 1, 1);
SetCoeff(irreduc, 0, 1);
GF2E::init(irreduc);

and then I also initialize two polynomials:

GF2X a; 
SetCoeff(a, 120);
SetCoeff(a, 22);

GF2X b;
SetCoeff(b, 128);
SetCoeff(b, 51);

std::cout << "a: " << a << '\n';
std::cout << "b: " << b << '\n';

and multiply them:

std::cout << "\ndeg(a * b): " << deg(a * b) << '\n';

The output is deg(a * b): 248, which is out of the field/ring of the 2^128, defined by the irreducible polynomial.

I know that I am probably missing something obvious but I am very new to this area so bear with me.

Thank you!

Answer 1

As you already said, GF2X represents polynomials over GF2, so they do not get reduced by the polynomial you initialized GF2E with. You need to convert the polynomials to GF2E and then everything works as expected.

So changing you last line to

std::cout << "\ndeg(a * b): " << deg(conv<GF2X>(conv<GF2E>(a) * conv<GF2E>(b))) << '\n';

results in the output

deg(a * b): 124

This conversions are pretty ugly. I'm not sure if there is a better way to do it and the way NTL is documented it is hard to find the right functions for what you want to do. I only found GF2E::degree(), but this only gives you the degree if the irreducible polynomial. Let me know when you find the right way to do it.