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++?

It's really unclear what you are doing - you say you used eigen to do this in past - what has changed now since you don't use that ? — darune, Oct 15 '19 at 07:36
You need to implement (or find an implementation of) the field you want to use and then mostly follow the steps of this page: http://eigen.tuxfamily.org/dox/TopicCustomizing_CustomScalar.html -- probably not everything will work out of the box for "unusual" types (e.g., good pivoting will likely be different than what Eigen does). — chtz, Oct 15 '19 at 07:46
@darune I think the OP only used Eigen for `double` types, but used Matlab for GF types so far. — chtz, Oct 15 '19 at 07:48
@darune I have used Eigen for operations between matrices of type double. — DragHenry, Oct 15 '19 at 09:21
I have answered the question, but I fear the author will not check this post, 2 years and a half after its publishing ... — Dimitri Lesnoff, Apr 25 '22 at 15:28

score 1 · Answer 1 · answered Apr 25 '22 at 15:25

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.

GF(2^6) is such a small field that it is definitely better to cache a multiplication table and a division table than using such a library. Addition table is useless as it's the xor operation. — WhatsUp, Apr 25 '22 at 15:31

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

1 Answers1