# Inverse of a polynomial in a polynomial ring

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}$

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[AlgebraPolynomialPowerModPolynomialPowerMod[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

• +1, great! While @Daniel Lichtblau's answer was very nice in that it made me learn a bit about Gröbner bases, this answer is excellent in its simplicity. Reading Mathematica's documentation, I think we can perform the task in an even simpler way: PolynomialMod[PolynomialRemainder[poly^-1, x^11 - 1, x], 32]. Am I right? – M.S. Dousti Jun 5 '13 at 20:19
• @Sadeq, that works, but I'm personally more inclined to use PolynomialPowerMod[], in the same manner that I'd use PowerMod[] for the modular inversion of a number. – J. M. will be back soon Jun 6 '13 at 1:18

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.