GF(28)运算

任务:
用C／C++实现对GF(2^8)的若干运算功能，包括：加法、乘法、求乘法逆元（给定x，求y，使得x*y == 1 )、求离散对数（即给定一个生成元g，输入x，求y使得g^y == x)。

首先分析一下思路：
加法思路：对每一位进行异或操作

乘法：
①（参照密码编码学与网络安全的书本还原的一个算法）首先计算数组a中的对数组b中每一位的乘法中间结果，然后根据数组b决定用来异或的中间结果，最后得出结果。
②利用无符号字符类型解释整形创建一个过度变量为result，然后根据字符b的最后一位决定结果值，如果b的最后一位是0则result等于上一个循环的result值，若b的最后一位是1，result值等于result异或a。需要做八次循环，每次循环一开始都要判断a是否大于127如果大于127则a需要左移一位并且异或1B，else a只需要左移一位。

乘法逆元思路：
首先规定生成元是3（00000011，当然用其他生成元也可以，随便）然后生成一个以3为生成元的逆元表，然后查询用户输入的x查询到x之后利用255减去x所在位置那个位置的元素即为x的乘法逆元y

离散对数思路：
用户输入生成元与X，多次调用乘法，调用乘法的次数则为所求的离散对数

我大概用到的函数定义（忽略界面函数，输入输出函数等与算法无关的函数）：

#include <iostream>
#include <cstring>
#include <fstream> 
using namespace std;
void set_genrator();           //用于开始设置生成元数组 
void set_Inverse();           //用于开始设置逆元表
unsigned char GFsum(unsigned char a, unsigned char b); //求和 
unsigned char GFmul(unsigned char a, unsigned char b); //乘法 
unsigned char inverse(unsigned char b);  //乘法逆元 
bool judge_genrator(unsigned char a); //判断用户输入的生成元是否为生成元 
int logarithm(unsigned char a, unsigned char b);  //离散对数
int Genrator[256];           //保存生成元信息
unsigned char Inverse[256];      //保存以3为生成元的逆元表

用于设置生成元数组用来判断用户输入的生成元是否为一个真实的生成元：

void set_genrator(){
	memset(Genrator, 0, sizeof(Genrator));
	string buf;
	int a;
	ifstream GEN("一个包含所有生成元的记录文件，可以自己生成也可以网上去找");
	while (!GEN.eof()){
		GEN >> buf;
		a = change_int(buf);
		Genrator[a] = 1;
	}
	GEN.close();
}

生成逆元表

void set_Inverse(){
	unsigned char gen = 3;
	Inverse[0] = 0;
	Inverse[1] = 3;
	for (int i = 2; i < 256; i++){
		Inverse[i] = GFmul(Inverse[i-1], gen);
	}
}

具体算法

加法：

//直接异或运算就ok了

}

乘法：

unsigned char GFmul(unsigned char a, unsigned char b){
	unsigned char result = 0;
	if ((b&1)==1) result = a;
	b = b >> 1;
	for (int i = 0; i < 8; i++){
		if ((a>127))
			a = (a << 1) ^ 0x1b;
		else 
			a = a << 1;
		if((b&1) == 1){
            result ^= a;
        }
        b >>= 1;
	}
	return result;
}

}

分析一下乘法原理：

总共要循环8次，每一次循环都需要判断b的最低位是否为1，a的最高位是否为1。如果b的最低位为1，那么就结果result就要与a进行异或运算。再判断a最高位是否为1，如果是的话那么a在左移之后还要异或 1B。大概差不多了吧。

乘法逆元：

//生成逆元表函数
void set_Inverse(){
	unsigned char gen = 3;
	Inverse[0] = 0;
	Inverse[1] = 3;
	for (int i = 2; i < 256; i++){
		Inverse[i] = GFmul(Inverse[i-1], gen);
	}
}
//查表函数
unsigned char inverse(unsigned char b){
	//初始化 
	unsigned char result;
	if (b == 0){
		cout << (int)b << "没有逆元" <<endl; //0没有逆元
	}
	else {
		for (int i = 1; i < 256; i++){
			if (Inverse[i] == b) {
				result = Inverse[255-i];
				return result;
			}
		}
	}
}

}

乘法逆元原理：

在GF(2^8)这个群里如果有g^x g^y == 1（g是其中一个生成元）那么就会有x+y == 255。回到函数里面，第一个我利用生成元：3做254次乘法（第一个元素是0第二个元素是3）得到了一个以3为生成元重新排列的群。第二个就是查表函数了。暴力搜索出b所在的位置，然后*255-b所在的位置的元素就是b的逆元。

离散对数：

void set_genrator(){
	memset(Genrator, 0, sizeof(Genrator));
	string buf;
	int a;
	ifstream GEN("一个包含有所有生成元的文件，可以自己生成，也可以上网找");
	while (!GEN.eof()){
		GEN >> buf;
		a = change_int(buf);
		Genrator[a] = 1;
	}
	GEN.close();
}
int genrator(unsigned char a, unsigned char b){ 
	if (b == 0){
		cout << (int)b << "没有离散对数！" <<endl; 
	}
	else{
		//多次使用乘法直到找到为止；
		unsigned char mi = 1; 
		int y = 0;
		while(1){
			mi = GFmul(mi, a); 
			y++;
			if(mi == b) return y;
		}
	}
}

离散对数原理：

这里需要用户输入一个“生成元”和一个X，首先要保证用户输入的生成元是一个真实的生成元。所以需要加一个判断。之后就是利用生成元做多次乘法做到值为X为止，循环次数就是离散对数了。

最后：仅是学生党随意写的用于交流学习，不喜勿喷，谢谢驻足的各位