找到一个多项式的逆（倒数）模另一个多项式在有限域中的系数

Question

如果我有一个多项式 P，有没有办法计算 P^-1 模 Q，Q 是另一个多项式？我知道两个多项式的系数都属于整数模z的域，z是一个整数。

我不确定 SymPy 是否已经在其 galoistools 模块中提供了该功能。

Answer 1

这与寻找满足 PS + QT = 1 的多项式 S、T 基本相同。当 gcd(P, Q) = 1 时这是可能的，并且可以通过 [=17= 完成].例如，让我们用系数字段 Z/11Z:

反转 3x^3+2x+4 模 x^2+2x+3

from sympy.polys.domains import ZZ
from sympy.polys.galoistools import gf_gcdex

p = ZZ.map([3, 0, 2, 4])
q = ZZ.map([1, 2, 3])
z = 11
s, t, g = gf_gcdex(p, q, z, ZZ)
if len(g) == 1 and g[0] == 1: 
    print(s)
else:
    print('no inverse')

这会打印 [8, 5] - 相反的是 8x+5。手动完整性检查：

(3x^3+2x+4)*(8x+5) = 24x^4 + 15x^3 + 16x^2 + 42x + 20 
                   = 2x^4 + 4x^3 + 5x^2 + 9x + 9
                   = (x^2 + 2x + 3)*(2x^2 - 1) + 1
                   = 1 mod q

找到一个多项式的逆（倒数）模另一个多项式在有限域中的系数

Find the inverse (reciprocal) of a polynomial modulo another polynomial with coefficients in a finite field

python

sympy

galois-field