c - 这段代码对应的矩阵/vector 运算是什么？

Question

这是代码:

long long mul(long long x)
{
    uint64_t M[64] = INIT;
    uint64_t result = 0;

    for ( int i = 0; i < 64; i++ )
    {
        uint64_t a = x & M[i];
        uint64_t b = 0;
        while ( a ){
            b ^= a & 1;;
            a >>= 1;
        }
        result |= b << (63 - i);
    }
    return result;
}

此代码实现了 GF(2) 上的矩阵和 vector 的乘法。该代码将结果返回为 64x64 矩阵 M 和 1x64 vector x 的乘积。

我想知道这段代码的线性代数运算(在 GF(2) 上)是什么:

long long unknown(long long x)
{
    uint64_t A[] = INIT;
    uint64_t a = 0, b = 0;

    for( i = 1; i <= 64; i++ ){
        for( j = i; j <= 64; j++ ){
            if( ((x >> (64-i)) & 1) && ((x >> (64-j)) & 1) )
                a ^= A[b];
            b++;
        }
    }
    return a;
}

Answer 1

I want to know what linear algebraic operation( on GF(2) ) this code is:

当然，您指的是 GF(2)⁶⁴，即 GF(2) 上的 64 维 vector 域。

首先考虑循环结构:

    for( i = 1; i <= 64; i++ ){
        for( j = i; j <= 64; j++ ){

这是查看每对不同的索引(索引本身不一定彼此不同)。这应该提供第一个线索。然后我们看到

            if( ((x >> (64-i)) & 1) && ((x >> (64-j)) & 1) )

，测试 vector x是否同时设置了位i和位j。如果是，那么我们通过 vector 和(==逐元素异或)将一行矩阵A添加到累加变量a中。通过在每次内循环迭代中递增 b，我们确保每次迭代服务于 A 的不同行。这也告诉我们 A 必须有 64 * 65/2 = 160 行(这一点很重要)。

一般来说，这根本不是线性运算。 GF(2) 上 vector 场上的运算 o 为线性的标准归结为该表达式适用于所有 vector 对 x 和 y:

    o(x + y) = o(x) + o(y)

现在，为了符号方便，我们考虑字段 GF(2)² 而不是 GF(2)⁶⁴；只需添加零即可将结果从前者扩展到后者。令 x 为位 vector (1, 0)(例如，用整数 2 表示)。令 y 为位 vector (0, 1)(用整数 1 表示)。让 A 成为这个矩阵:

1 0
0 1
1 0

您的操作结果如下:

operand   result   as integer   comment
 x        (1, 0)      2         Only the first row is accumulated
 y        (1, 0)      2         Only the third row is accumulated
 x + y    (0, 1)      1         All rows are accumulated

显然，对于此 x、y< 来说，o(x) + o(y) = o(x + y) 的情况并非如此 和特征 A，因此该 A 的操作不是线性的。

有一些矩阵A其相应的运算是线性的，但是它们代表什么线性运算将取决于A。例如，可以用这种方式表示各种矩阵 vector 乘法。我不清楚矩阵 vector 乘法以外的线性运算是否可以用这种形式表示，但我倾向于认为不能。