`GF2::Matrix` — Powers of a Bit-Matrix

Raises a square bit-matrix to a power \(n\) or \(2^n\) respectively.

template<std::unsigned_integral Block, typename Allocator>
constexpr Matrix<Block, Allocator>
pow(const Matrix<Block, Allocator> &M, std::size_t n);     (1)

template<std::unsigned_integral Block, typename Allocator>
constexpr Matrix<Block, Allocator>
pow2(const Matrix<Block, Allocator> &M, std::size_t n);    (2)

1	Returns \(M^n\).
2	Returns \(M^{2^n}\). For example, we can raise \(M\) to the power \(2^{128}\) which is not representable as a typical `std::size_t`.

The powers are efficiently computed using using repeated squaring. It is also worth noting that all arithmetic in GF(2) is done mod 2 so there are no overflow issues even for large \(n\).

The input matrix must be square. That is checked using the gf2_assert macro. That check can be disabled by setting the GF2_NDEBUG flag at compile time.

Example

#include <GF2/GF2.h>
int main()
{
    auto M = GF2::Matrix<>::random(4);
    std::cout << "M:\n"             << M            << '\n';
    std::cout << "M^2:\n"           << pow(M,2)     << '\n';    (1)
    std::cout << "M^{256}:\n"       << pow(M,256)   << '\n';    (2)
    std::cout << "M^{2^8}:\n"       << pow2(M,8)    << '\n';    (3)
    std::cout << "M^{2^{100}}:\n"   << pow2(M,100)  << '\n';    (4)
}

1	Simple square of a small random bit-matrix.
2	Raise to the power \(256\) using `pow`.
3	Raise to the power \(2^8 = 256\) using `pow2`.
4	Raise to the power \(2^{100} = 1,267,650,600,228,229,401,496,703,205,376\).

Output

M:
1110
0001
0110
0111
M^2:
1001
0111
0111
0000
M^{256}:
1001
0000
0000
0000
M^{2^8}:
1001
0000
0000
0000
M^{2^{100}}:
1001
0000
0000
0000

GF2::Matrix — Powers of a Bit-Matrix

`GF2::Matrix` — Powers of a Bit-Matrix