最近在复习现代密码理论中的AES，AES中的字节变换的核心操作就是求 G F ( 2 8 ) GF(2^8) GF(28)上的多项式逆元，这个问题困扰了我一段时间，今天终于得到解决，其实计算方式和数论中求两个数的Bezout算法是一样的，这里感谢数论老师教给我们的用矩阵行初等变换的方法求Bezout，进而求逆元。
设 a , b ∈ Z a,b\in\mathcal{Z} a,b∈Z，则 a , b a,b a,b的最大公约数可以表示为 g c d ( a , b ) = d = s a + t b gcd(a,b) = d = sa + tb gcd(a,b)=d=sa+tb 把 d = s a + t b d = sa + tb d=sa+tb称作Bezout恒等式。
这里以一个具体的实例来说明,求 g c d ( 5 , 177 ) gcd(5,177) gcd(5,177)。
先把欲求的两个数写成如下的矩阵形式,即是以5和17为第一列，后面拼一个单位矩阵。 [ 177 1 0 5 0 1 ] \left[\begin{matrix} 177 & 1 & 0\\ 5 & 0 & 1 \\ \end{matrix}\right] [17751001]
将上述矩阵行初等变换至5和17这两个位置任意一个为0即可，另一个位置的值就是a和b的最大公约数。 [ 0 ∗ ∗ 1 − 2 71 ] \left[\begin{matrix} 0 & * & *\\ 1 & -2 & 71 \\ \end{matrix}\right] [01∗−2∗71]
得到Bezout恒等式,上述两个*位置表示这个问题中，不需要关注那两个位置的值 1 = 177 ∗ − 2 + 71 ∗ 5 1 = 177*-2 + 71*5 1=177∗−2+71∗5
如果最大公约数为1,则可以方便的看出其中一个元素的逆元。上式两端同时模177 71 ∗ 5 ≡ 1 m o d 177 71*5 \equiv 1 mod 177 71∗5≡1mod177
这样就得到71和5在 Z 177 中 的 逆 元 \mathcal{Z}_{177}中的逆元 Z177中的逆元
求通过不可约多项式 x 8 + x 4 + x 3 + x + 1 x^8+x^4+x^3+x+1 x8+x4+x3+x+1构造的 G F ( 2 8 ) GF(2^8) GF(28)上 ( 09 ) H (09)_H (09)H在上的乘法逆元。
1. ( 09 ) H (09)_H (09)H转换为多项式( 09 ) H = 00001001 = x 3 + 1 (09)_H = 00001001 = x^3+1 (09)H=00001001=x3+1
2.求 x 3 + 1 x^3+1 x3+1在 x 8 + x 4 + x 3 + x + 1 x^8+x^4+x^3+x+1 x8+x4+x3+x+1上的逆元,构造矩阵 [ x 8 + x 4 + x 3 + x + 1 1 0 x 3 + 1 0 1 ] \left[\begin{matrix} x^8+x^4+x^3+x+1 & 1 & 0\\ x^3+1 &0 &1 \\ \end{matrix}\right] [x8+x4+x3+x+1x3+11001]3.行初等变换至标准形式(注意合并多项式的时候系数是模2加法)4.具体的变换步骤，这里就不详细展开，但给出变换的顺序 r 1 − x 5 r 2 r_1 - x^5r_2 r1−x5r2 r 1 − x 2 r 2 r_1 - x^2r_2 r1−x2r2 r 1 − x r 2 r_1 - xr_2 r1−xr2 r 1 − r 2 r_1 - r_2 r1−r2 r 2 − x r 1 r_2 - xr_1 r2−xr1 r 1 − x 2 r 2 r_1 - x^2r_2 r1−x2r2 最后得到[ 0 ∗ ∗ 1 x x 6 + x 3 + x 2 + x + 1 ] \left[\begin{matrix} 0 & *& *\\ 1 &x&x^6+x^3+x^2+x+1\\ \end{matrix}\right] [01∗x∗x6+x3+x2+x+1]
显然 x 3 + 1 x^3+1 x3+1的逆元为 x 6 + x 3 + x 2 + x + 1 x^6+x^3+x^2+x+1 x6+x3+x2+x+1转换为2进制表示 01001111 01001111 0100111116进制表示 ( 4 F ) H (4F)_H (4F)H