[原创][RS]伽罗华域乘法和除法运算

假设所处的域为2^4的伽罗华域(域发生多项式为x^4+x+1)
下面我们计算a^9 * a^13:
GF(4)域的各个元素见以前的日志

其中a^9 = 10; a^13 = 13;
RSLT1 : (x^3+x)(x^3+x^2+1) = x^6+x^5+x^3+x^4+x^3+x 

由于域中的元素最高次幂不能大于4, 且乘积一定存在于
现在这个伽罗华域。则最后的结果要用RSLT1的结果模除
域发生多项式为x^4+x+1。
多项式除法类似于传统的长除法。其过程包括，先对除数
乘以一值以使其阶数与被除数相等，再将二者相减，然后
对余数重复进行上述操作，直至被除数的最低位参与运算。

运算过程如下：
             x^6 x^5 x^4 x^3 x^2 x^1 x^0
被除数：      1   1   1   0   0   1   0
除数 * x^2:   1   0   0   1   1
结果:             1   1   1   1   1
除数 * x^1:       1   0   0   1   1
结果:             1   1   0   0   0
除数 * x^0:       1   0   0   1   1
结果:                 1   0   1   1 

据此可知，商为x^2 + x + 1，而余数，亦即a^9 * a^13的
最终结果为x^3 + x + 1，也就是十进制数11。

所以 a^9 * a^13 = a^7.

两个迦罗华域元素的除法运算通常通过乘以除数的倒数来完成。
任一域元素的倒数被定义为当乘以其自身时使得所获乘积为1的
那个域元素。同样，任一域元素的倒数有且仅有一个。

本文地址：http://114er.blogspot.com/2010/10/rs_21.html 原创文章如转载，请注明链接： 转自Welcome Funny Guys