以下是代码：
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;
}
我想知道这个代码是什么线性代数运算(在GF(2(上(：
当然你指的是GF(2(64，GF(2。
首先考虑环路结构：
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
显然，对于该x、y和特性A，不是o(x) + o(y) = o(x + y)的情况，因此对于该A，运算不是线性的。
有一些矩阵A的对应运算是线性的，但它们表示的线性运算将取决于A。例如，可以用这种方式表示各种各样的矩阵向量乘法。我不清楚矩阵向量乘法以外的线性运算是否可以用这种形式表示，但我倾向于不这样认为。