Find the linear transformation

Question

Given a set of bit vectors \$A\$ and a binary matrix \$M\$, we can define the set \$MA = \{ Mx : x \in A \}\$, where \$ M x \$ is the result of the matrix multiplication of \$ M \$ by \$ x \$ over \$\mathbb{F}_2\$, the field with two elements.

Given the set \$ A \$ and the set \$ M A \$, your task is to recover a possible value for \$ M \$ in as little time as possible.

Note that since these are sets, they are unordered.

Scoring

For all pairs of integers \$ 0 < a \leq 15\$, \$a < b \leq 32\$, I produced a random \$32 \times b\$ binary matrix \$M\$, a set \$ A \$ of size \$2^a\$ with random vectors of size \$ b \$, and calculated \$ M A \$.

Your score is the time you take to solve all these samples.

I/O

Your program will recieve input from stdin in the following format:

t
b1 n1
x1 x2 x3 x4 ... xn1
y1 y2 y3 y4 ... yn1
...
bt nt
x1 x2 x3 x4 ... xnt
y1 y2 y3 y4 ... ynt

t is the number of instances of the problem you are required to solve. For each instance, you will get the number b, the number of bits in the input, and n, the number of vectors. In the next line, you will get n integers \$0 \leq x < 2^b\$, whose binary representation is the input vectors. In the following line, you will get the n integers \$0 \leq x < 2^{32}\$ whose binary representation is the vectors in \$MA\$.

You are to output t lines to stdout in the format

x1 x2 ... x32
x1 x2 ... x32
...
x1 x2 ... x32
x1 x2 ... x32

each containing 32 integers \$0 \leq x < 2^b\$ representing the rows of \$ M \$.

Example

For the input

1
7 16
5 14 21 23 26 36 38 45 55 74 76 80 95 100 109 123 
114917382 260133574 340793034 1730627271 1755714561 1818746903 2816946300 2860390058 3157685360 3190685792 3599242337 3720917681 3919737131 4067636519 4180906999 4260521953 

A possible matrix is

48 43 76 13 102 126 98 125 88 51 76 69 72 27 76 115 89 11 33 29 0 96 64 87 64 39 48 118 61 115 78 43 

Under this matrix, 0000101 (5), for example, comes out to be 01101100011001111110000000010111 (1818746903)

Rules

• Standard loopholes are disallowed.
• The programming language you use must be freely available.
• Add instructions on how to compile and run your code.
• The code will be timed on my computer which has Intel Core i7-9700 with 8 threads and 32GB RAM.
• You may not exploit the PRNG (e.g. find its seed and from that find which matrices were generated).
• You may assume all other properties implied by the generation method (e.g. that n is a power of two, or that the sets are given sorted).

This is the code used to generate the samples (on stdout, stderr just logs the matrices, which of course won't be provided to your program):

#include <set>
#include <assert.h>
#include <random>
#include <iostream>
#define maxv(b) (b==32?-1u:(1u<<b)-1u)

uint32_t matmul(uint32_t M[32], uint32_t x) {
    uint32_t ans = 0;
    for (int i = 0; i < 32; i++) ans |= ((uint32_t)__builtin_parity(M[i] & x)) << (31-i);
    return ans;
}

std::mt19937 rng(time(0));

int main() {
    std::cout << "360\n";
    for (int a = 1; a <= 15; a++) {
        for (int b = a+1; b <= 32; b++) {
            std::set<uint32_t> A;
            uint32_t M[32];
            for (int i = 0; i < 32; i++) {
                M[i] = std::uniform_int_distribution<uint32_t>(0, maxv(b))(rng);
                std::cerr << M[i] << ' ';
            }
            std::cerr << '\n';
            std::set<uint32_t> MA;
            for (int i = 0; i < 1<<a; i++) {
                uint32_t x;
                do x = std::uniform_int_distribution<uint32_t>(0, maxv(b))(rng); while (A.count(x));
                A.insert(x);
                MA.insert(matmul(M, x));
            }
            assert(A.size()==MA.size());
            std::cout << b << ' ' << (1<<a) << '\n';
            for (uint32_t a : A) std::cout << a << ' ';
            std::cout << '\n';
            for (uint32_t a : MA) std::cout << a << ' ';
            std::cout << '\n';
        }
    }
}
```