ComCom作业五：GF(2^8)的乘法（选做）

密码学

0、证明({0,1}^8，XOR)是群。即8比特二进制串在异或操作下是群。[提示：容易，请验证群的四个公理]

　　1. 封闭性。两个长度为8比特的数进行亦或操作也一定为一个8比特的数，因此满足封闭性。
　　2. 结合律。对于三个比特任意交换次序进行亦或操作结果总是一样的，因此对于任意三个8比特的数来说，是满足结合律的。
　　3. 单位元。单位元是0。
　　4. 逆元。逆元是这个数本身。

1、证明当x = 2 的时候，f_2(y)是单射、满射。

　　任选z且y != z。证明 f_2(z) != f_2(y)。
　　1. 假设y和z最高比特位相同，那么其余的比特位是肯定不相同的。因此，进行移位操作或者是进行移位亦或操作以后都不可能是相同的。
　　2. 假如y的最高位为0，z的最高位是1。那么f_2(y)的最低位肯定为0，f_2(z)最低位肯定为1，因此也不相等。
　　所以，f_2(y)是单射的。遍历G里面的所有元素都能映射到唯一的一个值，因此最后映射的结果大小也为G。因此是满射的。

2、在以上的基础上，证明对任意的x，f_x(y)是单射、满射。[提示：乘法无非就是乘2与XOR的组合]

　　使用反证法证明单射。
　　假设y和z属于G 且 $y$ != $z$，使得$f_x(y) = f_x(z)$
　　所以，$x*y = x*z$
　　又因为乘x只是乘2和XOR的组合，因此可以满足分配律
　　因此，(y XOR z) * x = 0，矛盾！
　　同样证明满射可以用映射前后的集合一样大就可以得出满射。

3、从证明的过程当中，我们是否可以发现GF(2^8)的乘法是满射且单射的端倪？也就是说，我们能立即找到一个不是1B的模数来满足单射、满射的要求吗？如果可以，请给出，并编程验证自己的想法是正确的。

　　猜想：只要能够让进行的亦或那个数最低位为1就好了。（因为这是前面证明乘2是单射的所使用的一个条件）
　　测试结果发现，猜想是错误的。但还是找到了一些满足条件的模数。

测试截图：

代码：

# include<iostream>
using namespace std;
int mod = 0x1b;
//定义G(2^8)中的 x*2
int mul2(int x){
    if (x&0x80) return ((x << 1) ^ mod)&255;     //&255表示 只取一个字节
    else return (x << 1)&255;
}
//G(2^8)乘法
int mul(int x, int y) {
    int r = 0, tmp = x;
    while (y) {
        if (y % 2) r ^= tmp;     //加法取模相当于亦或
        tmp = mul2(tmp);
        y /= 2;
    }
    return r;
}
int a[256];
bool testArray() {
    for (int i = 0; i < 256; ++i)
        if (a[i] != 1)
            return false;
    return true;
}
void testModNumber() {
    for (int i = 1; i < 256; ++i) {
        for (int i = 0; i < 256; ++i)
            a[i] = 0;
        for (int j = 0; j < 256; ++j)
            a[mul(i, j)] = 1;
        if (!testArray()) {
            cout << hex << mod << " 不可以" << endl;
            return;
        }
    }
    cout << hex << mod << " 可以" << endl;
}
int main() {
    mod = 0x11;
    // 测试奇数是否可以作为模数
    for (int i = 1; i < 10; ++i) {
        mod += 2;
        testModNumber();
    }
    system("pause");
    return 0;
}