在有限域中怎么求一个多项式的逆元

2025-03-13 00:28:10

推荐回答（2个）

回答1：

把生成这个有限域的生成多项式作为模多项式，用辗转相除法（欧几里得算法）不停模生成多项式得余式直到1（肯定是1啊，因为给出的多项式有逆元，和模多项式互质的）。（可能模多项式次数比给出的多项式次数高，第一步除以模多项式，商式是0，余式是给出的多项式）
然后如同求ax=1(mod m)一样反向进行，把1用模多项式和给出的多项式的“线性组合”表示出来，给出的多项式的“系数”多项式就是这个多项式的逆元啦。

可以检查一下算错没有，求出逆元后和给出的多项式在模生成多项式下相乘，看是否等于1。

过程中涉及多项式长除法，挺费纸的。
我在百度搜到几篇博客，都是通过mod（x^(n/2)）找到与mod(x^n)的关系，求解方法还涉及FFT,这应该属于偏工程的算法吧，没仔细看不是很清楚。

回答2：

你好，求逆元，要看具体的运算规则是啥，
只要满足x*y=0（注意*是群中定义的运算，不是普通的数字乘法，另外其中0是单位元）
x与y互为逆元。