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
- whether the inverse polynomial $f_q(x)$ exists; and
- 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}$