Inverse of a polynomial in a polynomial ring

Question

Let $N$ be a prime, and $q$ be a positive integer. Given a polynomial $f(x)$ in $R = \mathbb Z[x]/(x^N-1)$, I want to find another polynomial $f_q(x)$ in $R_q = \mathbb Z_q[x]/(x^N-1)$, such that

$$f(x)f_q(x)=1 \pmod q$$

I want Mathematica to tell me

1. whether the inverse polynomial $f_q(x)$ exists; and
2. if so, find $f_q(x)$.

Examples for $N=11$ and $q=32$ are cited from Wikipedia's entry on NTRUEncrypt:

$f(x) = -1 + x + x^2 - x^4 + x^6 +x^9 - x^{10}$

$f_q(x) = 5 + 9x + 6x^2 + 16x^3 + 4x^4 + 15x^5 + 16x^6 + 22x^7 + 20x^8 + 18x^9 + 30x^{10}$

Answer 1

As it turns out, there's an (undocumented) function eminently suitable for the task:

poly = -1 + x + x^2 - x^4 + x^6 + x^9 - x^10;
PolynomialMod[Algebra`PolynomialPowerMod`PolynomialPowerMod[poly, -1, x, x^11 - 1], 32]
   5 + 9 x + 6 x^2 + 16 x^3 + 4 x^4 + 15 x^5 + 16 x^6 + 22 x^7 + 20 x^8 + 18 x^9 + 30 x^10

Check the result:

PolynomialMod[PolynomialRemainder[poly %, x^11 - 1, x], 32]
   1

---

If you're the conservative sort, and you're not too keen on the use of undocumented functions, then you might want to remember that the extended Euclidean algorithm is a very useful thing for the computation of modular inverses (Bézout's identity):

PolynomialMod[PolynomialExtendedGCD[-1 + x + x^2 - x^4 + x^6 + x^9 - x^10,
                                    x^11 - 1, x][[2, 1]], 32]
   5 + 9 x + 6 x^2 + 16 x^3 + 4 x^4 + 15 x^5 + 16 x^6 + 22 x^7 + 20 x^8 + 18 x^9 + 30 x^10

Answer 2

Use a Gröbner basis.

The idea is to set up an equation for this multiplicative inverse, in a ring where both $x^{11}-1$ and $32$ are zero (that is, $\mathbf Z[x]/(32,x^{11}-1)$). Then unravel that equation using GroebnerBasis to get the variable representing this reciprocal to f in terms of x:

f = -1 + x + x^2 - x^4 + x^6 + x^9 - x^10;
defpoly = x^11 - 1;

Since we do not have a field for our coefficients, we compute a basis over the integers:

finv = First[finv /. Solve[Last[
             GroebnerBasis[{f*finv - 1, defpoly, 32}, {finv, x}, 
                           CoefficientDomain -> Integers]] == 0, finv]]

(* Out[97]= 5 + 9 x + 6 x^2 - 16 x^3 + 4 x^4 + 15 x^5 - 16 x^6 - 
 10 x^7 - 12 x^8 - 14 x^9 - 2 x^10 *)

finv = PolynomialMod[finv, 32]

(* Out[98]= 5 + 9 x + 6 x^2 + 16 x^3 + 4 x^4 + 15 x^5 + 16 x^6 + 
 22 x^7 + 20 x^8 + 18 x^9 + 30 x^10 *)

For more (perhaps painfully more) applications of such bases, here is a PDF link.