python - 找到一个多项式的逆（倒数）模另一个具有有限域系数的多项式

Question

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

我不确定 SymPy 是否已经在其galoistools模块中具有此功能。

Answer 1

这基本上与找到多项式 S, T 使得 PS + QT = 1 相同。这在 gcd(P, Q) = 1 时是可能的，并且可以用 来完成galoistools.gf_gcdex。例如，让我们用系数字段 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