利用指数表和对数表，实现GF(2^8)的乘法优化。
首先利用简单的基础的GF(2^8)乘法，构造指数表和对数表。在这里选取生成元3。
指数表exp[i] = 3^i，对数表log[i] = log3(i)。
要实现x 与 y 相乘，首先利用对数表找出3^m = x, 3^n = y，这时的乘法就是 x * y = 3^m * 3^n = 3^(m+n)，然后利用指数表找到exp[m+n]对应的值。
因此所有的乘法都变成了查表操作，提高了效率。但是对于数域较大时，保存对数表和指数表的空间要求较高。典型的牺牲空间换取时间。
#include<iostream>
#include<fstream>
using namespace std;
unsigned char exp[]; //exp[i] = 3^i
unsigned char log[]; //log[i] = log3(i) unsigned char GFmul(unsigned char a, unsigned char b){
//GF(2^8) 乘法
unsigned char result = ;
if((b&) == )result = a;
b >>= ;
for(int i = ; i < ; i ++){
if(a > ){
a = (a << ) ^ 0x1b;
}
else{
a <<= ;
}
if((b&) == ){
result ^= a;
}
b >>= ;
}
return result;
}
void generateMulTab(){
//选择生成元3作为构造乘法表的基础
const int N = ;
unsigned char tmp = ;
for(int i = ; i < ; i ++){
tmp = GFmul(tmp, N);
exp[i] = tmp;
log[tmp] = i;
}
}
unsigned char GFfastMul(unsigned char x, unsigned char y){
//利用exp和log来查表实现乘法
if(x == || y == )return ;
//x = 3^m, y = 3 ^ n; x * y = 3^m * 3^n = 3^(m+n)
int m = log[x], n = log[y];
return exp[(m+n)>?(m+n-):(m+n)];
} int main(){
//单元测试，乘法打表
generateMulTab();
int count[];
for(int i = ; i < ; i ++)count[i] = ;
unsigned char x, y;
x = ;
do{
y = ;
do{
count[GFfastMul(x, y)] ++;
y ++;
}while(y != );
x ++;
}while(x != );
ofstream write("Test.txt");
for(int i = ; i < ; i ++)write<<i<<"\t"<<count[i]<<endl;
write.close();
return ;
}
C++