有限域的运算.doc

《有限域的运算.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、有限域GF（2n）运算  在研究的数字电路系统中，如加解密算法、信道编码和数字信号处理等领域会涉及近似代数的相关理论，如群伦、Galois域等基础知识。同时我们引入概念，域。一个域是一组元素的集合，它可以在集合中完成加减乘除等四则运算。加法和乘法必须满足交换、结合和分配的规律。    给定一个集合G，在其上定于了一个二元运算*。    交换：对于G中任意的元素a和b，满足a*b=b*a，则G称为交换群（Abel群）    结合：二元运算*具有结合性，即对任何a,b,c属于G，a*(b*c)=(a*b)*c.    分配：对于F域中任意三个元素a,b,c，有a*(b+c)=a*b+

2、a*c;域中元素的个数称为域的阶（order），此时该域的阶为3.    有限域多项式：    GF(2)=x^6+x^4+x^2+x+1等价于比特串，即16进制表示的57。    1、有限域加法    多项式之和等于先对具有相同x次幂的系数求和，然后各项再相加。而各系数求和是在域F中进行的；c(x)=a(x)+b(x)等价于ci=ai+bi     2、有限域乘法    多项式乘法关于多项式加法满足结合律、交换律和分配律。单元元素为x0项的系数等于1和0次多项式。为使乘法运算在F域上具有封闭性，选取一个1次多项式m(x),当多项式a（x）和b(x)的乘积定义为模多项式m(x)下

3、的多项式乘积：C(x)=a(x).b(x)等价于c(x)恒=a(x)*b(x)   (modm(x))    二进制域GF（2）在编码理论扮演重要的角色，而在数字计算机和数据传输或是存储系统中同样得到了普遍的运用。    在多项式表达中，有限域2^8内的乘法就是乘法所得到的结果经一个不可约简的8次二进制多项式取模后的结果。不可约简的多项式是指多项式除了它本身和1以外没有其他的因式。Rijndael中这个多项式被命名为m（x），定义如下：m(x)=x^8+x^4+x^3+x+1    (b7b6b5b4b3b2b1b0)*'01'=（b7b6b5b4b3b2b1b0）    (b7

4、b6b5b4b3b2b1b0)*'02'=（b6b5b4b3b2b1b00）+(000b7b70b7b7)    (b7b6b5b4b3b2b1b0)*'03'=（b7b6b5b4b3b2b1b0）*'01'+(b7b6b5b4b3b2b1b0)*'02'记为xtime（）。乘以一个高于一次的多项式可以通过反复使用xtime（）操作，然后将多个中间结果相加的方法来实现。有限域上的乘法（全面理解）对于有限域GF(256),可以先计算出其乘法表。   在GF(256)中，加法就是异或运算，任意一个元素都可以表示成GF(2)   上的一个最多7次的多项式，   所以   0=000  

5、就是0   1=001  就是1   2=0010就是x+0=x   3=0011就是x+1   4=00100就是x^2   然后对于两个变量   u,v   可以先计算两个对应多项式的乘积（需要注意的是加法是模2的，或者说是异或运算），   比如   3*7=(x+1)*(x^2+x+1)=x*x^2+x*x+x+x^2+x+1=x^3+1  (模2运算中x+x=0  and x^2+x^2=0)   所以3*7=9   在乘积得出来的多项式次数大于7时，我们需要对多项式在GF(2)上关于h(x)求余数，也就是   129*5=(x^7+1)*(x^2+1)=x^9+x^7+

6、x^2+1   将上面的函数加上x*h(x)可以消去x^9,这里的h(x)是既约多项式x^8+x^4+x^3+x^2+1，（其实就是手工除法过程，只是现在每一次商总是0或1），所以   129*5=x^9+x^7+x^2+1+x^9+x^5+x^4+x^3+x=x^7+x^5+x^4+x^3+x^2+x+1   ==191   在得出乘法表以后，我们可以很快的从表格中对于每一个元素找到它的逆，于是逆运算也有了，除法就可以分解为乘法和逆运算。   有了加乘逆以后（对于GF(2^n)减法同加法没有分别）   就可以使用手工除法了