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