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

Question

If I have a polynomial P, is there a way to calculate P^-1 modulo Q, being Q another polynomial? I know that the coefficients of both polynomials belongs to the field of integers modulo z, being z an integer.

I´m not sure if SymPy has already a function for that in its galoistools module.

Answer 1

This is essentially the same as finding polynomials S, T such that PS + QT = 1. Which is possible when gcd(P, Q) = 1, and can be done with galoistools.gf_gcdex. For example, let's invert 3x^3+2x+4 modulo x^2+2x+3 with the coefficient field 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')

This prints [8, 5] - the inverse is 8x+5. Sanity check by hand:

(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