Найти обратный (обратный) полинома по модулю другого полинома с коэффициентами в конечном поле

Question

Если у меня есть полином P, есть ли способ вычислить P ^ -1 по модулю Q, будучи Q еще одним полиномом?Я знаю, что коэффициенты обоих полиномов принадлежат области целых чисел по модулю z, будучи z целым числом.

Я не уверен, что SymPy уже имеет функцию для этого в своих galoistools модуль.

Answer 1

По сути, это то же самое, что и нахождение полиномов S, T, таких что PS + QT = 1. Это возможно, когда gcd (P, Q) = 1, и это можно сделать с помощью galoistools.gf_gcdex.Например, давайте инвертируем 3x^3+2x+4 по модулю x^2+2x+3 с полем коэффициента Z / 11Z:

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