Performing matrix-operations (e.g. product and inverse) over GF(2^6) in C++

Question

I want to implement some matrix operations such as product and inverse computation over a Galois Field GF(64) in C++ language. I have normally used Eigen library to perform such operations in double type.

In Matlab it is possible to convert a matrix over a GF using the function: A_gf = gf(A, 6); all the subsequent operations defined on A_gf are automatically done in a GF(64), such the inverse of A: inv(A).

Do you know if I can do something similar in C++?

Answer 1

Eigen does not support finite field arithmetic up to my knowledge. The only types natively supported are the native types.

As precised in the comments, you can add your own custom types : eigen.tuxfamily.org/dox/TopicCustomizing_CustomScalar.html

You are better off using either FLINT or NTL libraries.

Since your finite field has characteristic 2 (because the order is a power of 2), you can have optimized arithmetic in NTL with matrices over GF2E (GF(2^6) is an extension of GF(2)). https://libntl.org/doc/GF2E.cpp.html

So you probably want to use NTL over FLINT. You also want to make sure you use gf2x as backend, check the documentation for the installation of NTL.

For matrices over GF2E, here is the documentation : https://libntl.org/doc/mat_GF2E.cpp.html

#include<NTL/GF2XFactoring.h>
#include<NTL/GF2X.h>
#include<NTL/GF2E.h>
#include<NTL/mat_GF2E.h>
// The two first includes might not be necessary
using namespace NTL;
using namespace std;
int main()
{
  // You have to compute first a "good" polynomial as modulus, of degree 64.
  /* GF2X P = {(GF2)1, 1, 0, 1, 1, 0, 1}; */

  GF2X P;
  BuildSparseIrred(P, 6); // generate an irreducible polynomial P
                      // of degree 6 over GF(17)
  GF2E::init(P); // define GF(2^6)

  mat_GF2E m;  // declare matrices over GF(2^6)
  vec_GF2E x, b;
  GF2E d;
  random(m, 10, 10);
  random(b, 10);
  solve(d, x, m, b);
  cout << "Matrix : " << m << endl;
  cout << "vector : " << b << endl;
  cout << "The solution of the system M*x = b is :" << endl;
  cout << x << endl;
  /* (To be completed) */
  return 0;
}

Some cases are optimized for the polynomial modulus :

The GF2XModulus routines optimize several important special cases:

• f = X^n + X^k + 1, where k <= min((n+1)/2, n-NTL_BITS_PER_LONG)
• f = X^n + X^{k_3} + X^{k_2} + X^{k_1} + 1, where k_3 <= min((n+1)/2, n-NTL_BITS_PER_LONG)
• f = X^n + g, where deg(g) is small

It would thus be ideal to find a polynomial of one of the two first cases with degree 6 to speed up the computations.