GF2++

Overview

GF2++ is a C++ library that provides classes for boolean vectors and matrices — sometimes referred to as bit-vectors and bit-matrices.

In the jargon of professional mathematics the classes make it possible to perform linear algebra over GF(2), the simplest Galois Field with just two elements usually denoted 0 & 1 (or sometimes as the booleans, true & false, or as the bits, set & unset).

GF(2) is a mathematical field which just means that addition/subtraction and multiplication/division operations are defined. In fact these are are just the same arithmetic operations you learnt as a child but to keep things closed in the set \(\{0, 1\}\), in GF(2) they are defined mod 2.

In sum, bit-vectors and bit-matrices are distinguished by having elements that are either zero or one and by the fact that the usual arithmetic operations are performed mod 2.

The library is header-only so there is nothing to compile & link — just drop the small GF2/ include directory somewhere convenient and you are good to go. The corresponding namespace GF2 houses the two main classes GF2::Vector and GF2::Matrix.

A rich interface is provided to set up and manipulate bit-vectors and bit-matrices in various ways and of course to allow them to interact. Their elements are efficiently packed into storage blocks (the classes are templated over the block type which defaults to a 64-bit unsigned integer, a natural block for most modern computer architectures).

Because arithmetic in GF(2) is always done mod 2, it is easy to verify, in computer terms, that addition/subtraction becomes the XOR operation while multiplication/division becomes AND. Of course bit-twiddling operators like XOR and AND are fundamental for all processors. GF2++ uses the equivalences to perform most interactions on and between bit-vectors and bit-matrices very efficiently by working on whole blocks of elements at a time.

For example, this library makes it possible to quickly extract the characteristic polynomial for a square GF2::Matrix with millions of elements—​a problem that chokes a naive implementation that does not take into account the special nature of arithmetic in GF(2).

How To Use GF2++

GF2++ is header-only and all the source files are in the repository’s include/GF2/ directory. Simply drop that directory somewhere in your include path to use it.

Here is a simple example:

#include <GF2/GF2.h>                                    (1)
int
main()
{
    auto M = GF2::Matrix<>::random(6);                  (2)
    auto c = GF2::characteristic_polynomial(M);         (3)
    std::cout << "The GF2::Matrix:\n" << M << "\n";
    std::cout << "has a characteristic polynomial with coefficients: " << c << "\n\n";
    std::cout << "The characteristic polynomial sum of the bit-matrix (should be all zeros):\n";
    std::cout << GF2::polynomial_sum(c, M) << "\n";     (4)
    return 0;
}
1 There is a small convenience include-the-lot header GF2/GF2.h.
2 This creates a randomly filled \(6 \times 6\) bit-matrix M where 0 & 1 are equally probable to occur.
3 Extracts the coefficients for the characteristic polynomial of that matrix as a bit-vector c with seven elements.
The polynomial has the form \(c_0 + c_1 x + c_2 x^2 + ... + c_6 x^6\).
4 Verify that M satisfies its own characteristic equation (the Cayley Hamilton theorem):
\(c_0 I + c_1 M + c_2 M^2 + ... + c_6 M^6 = 0\) where \(I\) and \(0\) are the \(6 \times 6\) identity and zero matrices respectively.
Possible Output (the bit-matrix and characteristic polynomial varies from run to run):
The GF2::Matrix:
000011
111100
001010
001000
001011
010010
has a characteristic polynomial with coefficients: 0011111

The characteristic polynomial sum of the bit-matrix (should be all zeros):
000000
000000
000000
000000
000000
000000

Why Use GF2++?

The standard library already has std::bitset which is an efficient bitset class. In fact, recognizing that that class is familiar and well thought through, GF2::Vector replicates and extends much of that basic interface.

All std::bitset objects have a fixed size determined at compile time. The well known Boost library adds a dynamic version boost::dynamic_bitset where the size of the bitset can be set and changed at runtime.

As the two names suggest, in both the case of the standard library and Boost, the defined types are aimed at bitsets as opposed to bit-vectors. So for example, they print in bit-order with the least significant element/bit on the right. More importantly those classes don’t have any particular methods aimed at linear algebra. Neither does the standard library’s vector class std::vector.

On the other hand, there are several well known linear algebra libraries such as Eigen. Those are highly optimized for all the standard numeric types (floats, doubles, integers etc.) but they do not really handle GF(2) all that well. Sure you can create matrices of integers where all the elements are 0 or 1 but there is no builtin knowledge in those libraries that arithmetic is always performed mod 2.

For example, you might use Eigen to create an integer matrix of all 0’s and 1’s and then use a builtin function from that library to extract the characteristic polynomial. Modding the coefficients of that polynomial with 2 gets the appropriate version for GF(2). Technically this works but you will run in to overflow problems for even fairly modest sized matrices with just a few hundred rows and columns. Of course, you might use an underlying BitInt type that never overflows but then the calculations become dog slow for larger bit-matrices so that doesn’t help much.

If you work over GF(2) a specialized solution such as the one offered here is a much better way to go. This might be the case if for example, your interest is in certain areas of cryptography or random number generation.