-1

这是代码：

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) 上实现矩阵和向量的乘法。将结果作为 64x64 矩阵 M 和 1x64 向量 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;
}
4

1 回答 1

1

我想知道这个代码是什么线性代数运算（在 GF(2) 上）：

当然，您的意思是 GF(2) 64，即 GF(2) 上的 64 维向量域。

首先考虑循环结构：

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

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

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

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

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

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

现在，为了符号方便，让我们考虑字段 GF(2) 2而不是 GF(2) 64；只需添加零，就可以将结果从前者扩展到后者。设x为位向量 (1, 0)（例如，由整数 2 表示）。设y为位向量 (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

显然，o(x) + o(y) = o(x + y)对于 this x、y和特性A，情况并非如此，因此对于 this ，运算不是线性的A。

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

于 2018-07-30T15:17:01.820 回答