求域上多项式的逆元

问题描述

设域$\mathbb{F}=\mathbb{Z}_p[x]_{f(x)}$F=Zp​[x]f(x)​，其中$f(x)$f(x)为$\mathbb{Z}_p$Zp​上的不可约多项式，多项式$g(x)\in\mathbb{F}$g(x)∈F，求$g(x)$g(x)在$\mathbb{F}$F上的逆元。

求逆过程

先做辗转相除法：令$r_0=f(x),r_1=g(x)$r0​=f(x),r1​=g(x)
$\begin{aligned} r_0&=r_1q_1+r_2\ \dots\dots1\\ r_1&=r_2q_2+r_3\ \dots\dots2\\ &\dots\\ r_{n-2}&=r_{n-1}q_{n-1}+r_n\ \dots\dots n-1\\ r_{n-1}&=r_nq_n+r_{n+1}\ ,其中r_{n+1}=0\ \dots\dots n \end{aligned}$r0​r1​rn−2​rn−1​​=r1​q1​+r2​ ……1=r2​q2​+r3​ ……2…=rn−1​qn−1​+rn​ ……n−1=rn​qn​+rn+1​ ,其中rn+1​=0 ……n​

方法1：

因为$s(x)f(x)+t(x)g(x)=(f(x), g(x))$s(x)f(x)+t(x)g(x)=(f(x),g(x))，当$(f(x),g(x))=1$(f(x),g(x))=1时有：
$(t(x)g(x))_{f(x)}=(1-s(x)f(x))_{f(x)}=1$(t(x)g(x))f(x)​=(1−s(x)f(x))f(x)​=1所以$t(x)$t(x)即为$g(x)$g(x)在域$\mathbb{F}$F上的逆元。

其中$b_i=b_{i-2}-b_{i-1}*q_{n-i}$bi​=bi−2​−bi−1​∗qn−i​，$t(x)=b_{n-1}$t(x)=bn−1​。

方法2：

令$b_1=q_{n-1}$b1​=qn−1​，计算：

其中$b_i=b_{i-2}+b_{i-1}*q_{n-i}$bi​=bi−2​+bi−1​∗qn−i​。
  当$n$n为奇数时，$t(x)=b_{n-1}$t(x)=bn−1​；
  当$n$n为偶数时，$t(x)=-b_{n-1}$t(x)=−bn−1​；