xtime算法
xtime算法
理论基础：
C(x)=A(x)B(x) mod P(x)
二进制数转换为多项式:A(a7,a6,a5,a4,a3,a2,a1,a0)==>A(X)=a7x7+a6x6+a5x5+a4x4+a3x3+a2x2+a1x+a0，GF(28)内的最大值为(11111111)2==> x7+x6+x5+x4+x3+x2+x+1，P(x)=x8+x4+x3+x2+x+1==>(100011011)2=0x11B
X8 mod P(x)= x4+x3+x2+x+1——————x8除以P(x)的余数
异或运算：0⊕0=0, 0⊕1=1, 1⊕1=0
有限域GF(2n)加法：C(x)=A(x)+B(x)=∑cixi(0≤i≤m-1)，ci=ai+bi mod 2即ai⊕bi，A(x)=(am-1,…,a3,a2,a1,a0)2，B(x)=(bm-1,…,b3,b2,b1,b0)2
定义xtime()运算：设A(x)∈GF(28),A(x)=a7x7+a6x6+a5x5+a4x4+a3x3+a2x2+a1x+a0对应的二进制数为(a7,a6,a5,a4,a3,a2,a1,a0)则xtime(A(x))=xA(x)= a7x8+a6x7+a5x6+a4x5+a3x4+a2x3+a1x2+a0x对应的二进制数为(a7,a6,a5,a4,a3,a2,a1,a0,0)。将A(x)左移一位(最低位补0，原先的最高位删除)的结果为(a6,a5,a4,a3,a2,a1,a0,0)，如果a7=0，则A(x)左移一位的结果就是xtime(A(x))的值；如果a7=1,则A(x)左移一位的结果与0x1B逐比特异或(异或运算符⊕)即为xtime(A(x))的值。(a7=1时，x*A(x)的值超出GF(28)，需要 模P(x),结果为A(x) 左移一位的结果为(a6,a5,a4,a3,a2,a1,a0,0)与0x1B逐比特异或的值)
例题：
例题1：
设0x64∈GF(28)，求xtime(0x64)的值？
0x64转换为二进制数为(0110 0100)2，最高位a7=0,所以0x64左移一位的结果就是所求值，(0110 0100)2左移一位后的值为(110 01000)2
例题2：
在GF(28)中计算0x570x13的结果？
先将166进制数转换为二进制数：0x57=(0101 0111)2,0x13=(0001 0011)2
将二进制数转换为多项式：0x13=x4+x+1
0x570x13=0x57*(x4+x+1)=0x57x4+0x57x+0x57
0x57x就是xtime(0x57)=(1010 1110)2
0x57x2就是xtime(0x57x)=(0101 1100)+(0001 1011)=(0100 0111)2
同理0x57x3=(10001110)2,，0x57x4=(0000 0111)2
所以0x570x13=(00000111)2+(1010 1110)2+(0101 0111)2
