問題描述

設域$\mathbb{F}={\mathbb{Z}}_p[x{]}_{f(x)}$，其中$f(x)$為${\mathbb{Z}}_p$上的不可約多項式，多項式$g(x)\in \mathbb{F}$，求$g(x)$在$\mathbb{F}$上的逆元。

求逆過程

先做輾轉相除法：令$r_0=f(x),r_1=g(x)$
$$\begin{array}{rl}{r}_0& =r_1{q}_1+r_2\dots \dots 1\\ r_1& =r_2{q}_2+r_3\dots \dots 2\\ & \dots \\ r_{n?2}& =r_{n?1}{q}_{n?1}+r_n\dots \dots n?1\\ r_{n?1}& =r_n{q}_n+r_{n+1},其中r_{n+1}=0\dots \dots n\end{array}$$

方法1：

因為$s(x)f(x)+t(x)g(x)=(f(x),g(x))$，當$(f(x),g(x))=1$時有：
$$(t(x)g(x){)}_{f(x)}=(1?s(x)f(x){)}_{f(x)}=1$$所以$t(x)$即為$g(x)$在域$\mathbb{F}$上的逆元。

其中$b_i=b_{i?2}?b_{i?1}?q_{n?i}$，$t(x)=b_{n?1}$。

方法2：

令$b_1=q_{n?1}$，計算：

其中$b_i=b_{i?2}+b_{i?1}?q_{n?i}$。
??當$n$為奇數時，$t(x)=b_{n?1}$；
??當$n$為偶數時，$t(x)=?b_{n?1}$；

總結

以上是生活随笔為你收集整理的求域上多项式的逆元的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。