扩展欧几里得算法(Bezout恒等式)求有限域上多项式的乘法逆元

前言

最近在复习现代密码理论中的AES，AES中的字节变换的核心操作就是求$GF(2^8)$上的多项式逆元，这个问题困扰了我一段时间，今天终于得到解决，其实计算方式和数论中求两个数的Bezout算法是一样的，这里感谢数论老师教给我们的用矩阵行初等变换的方法求Bezout，进而求逆元。

Bezout恒等式

设$a,b\in \mathcal{Z}$，则$a,b$的最大公约数可以表示为
$$gcd(a,b)=d=sa+tb$$
把$d=sa+tb$称作Bezout恒等式。

矩阵的行初等变换求解Bezout恒等式

这里以一个具体的实例来说明,求$gcd(5,177)$。

• 先把欲求的两个数写成如下的矩阵形式,即是以5和17为第一列，后面拼一个单位矩阵。
  $$\left[\begin{array}{ccc}177& 1& 0\\ 5& 0& 1\end{array}\right]$$

• 将上述矩阵行初等变换至5和17这两个位置任意一个为0即可，另一个位置的值就是a和b的最大公约数。
  $$\left[\begin{array}{ccc}0& \ast & \ast \\ 1& -2& 71\end{array}\right]$$

• 得到Bezout恒等式,上述两个*位置表示这个问题中，不需要关注那两个位置的值
  $$1=177\ast -2+71\ast 5$$

• 如果最大公约数为1,则可以方便的看出其中一个元素的逆元。上式两端同时模177
  $$71\ast 5\equiv 1mod177$$

• 这样就得到71和5在${\mathcal{Z}}_{177}中的逆元$

求解$GF（2^8）$上的多项式乘法逆元

求通过不可约多项式$x^8+x^4+x^3+x+1$构造的$GF(2^8)$上$(09{)}_H$在上的乘法逆元。

• 1.$(09{)}_H$转换为多项式

$$(09{)}_H=00001001=x^3+1$$

• 2.求$x^3+1$在$x^8+x^4+x^3+x+1$上的逆元,构造矩阵
  $$\left[\begin{array}{ccc}{x}^8+x^4+x^3+x+1& 1& 0\\ x^3+1& 0& 1\end{array}\right]$$
• 3.行初等变换至标准形式(注意合并多项式的时候系数是模2加法)
• 4.具体的变换步骤，这里就不详细展开，但给出变换的顺序
  • $r_1-x^5{r}_2$
  • $r_1-x^2{r}_2$
  • $r_1-x{r}_2$
  • $r_1-r_2$
  • $r_2-x{r}_1$
  • $r_1-x^2{r}_2$
• 最后得到

$$\left[\begin{array}{ccc}0& \ast & \ast \\ 1& x& x^6+x^3+x^2+x+1\end{array}\right]$$

• 显然$x^3+1$的逆元为$x^6+x^3+x^2+x+1$
• 转换为2进制表示$01001111$
• 16进制表示$(4F{)}_H$