Decide whether a polynomial is invertible mod $q$

Question

When implementing NTRU related cryptosystem, I came across the problem of deciding whether a randomly generated polynomial is invertible mod $q$. How to solve it?

Answer 1

You are presumably working in a quotient of the polynomial ring $(\mathbb Z/q\mathbb Z)[x]$ by some polynomial $f$. (Typical examples: $f = x^p - x - 1$ or $f = x^p - 1$ where $p$ is a prime, $f = x^k + 1$ where $k$ is a power of 2.)

In this case, a polynomial $g \in (\mathbb Z/q\mathbb Z)[x]$ is invertible modulo $f$ if and only if $\gcd(f, g) = 1$, as usual. You can pick your favorite polynomial GCD algorithm to compute that.

In particular, you might have a tuple of integers $(g_0, g_1, g_2, \ldots, g_n)$ that, if read as $g_0 + g_1 x + g_2 x^2 + \cdots + g_n x^n$, variously represents an integer polynomial in $\mathbb Z[x]$, a representative of a coset in the quotient $\mathbb Z[x]/(f)$, a polynomial over the integers mod $q$ in $(\mathbb Z/q\mathbb Z)[x]$, and a representative of a coset in $(\mathbb Z/q\mathbb Z)[x]/(f)$.

If you compute the polynomial GCD in polynomials over $\mathbb Z/q\mathbb Z$, then you ascertain whether the coset in $(\mathbb Z/q\mathbb Z)[x]/(f)$ is invertible, or equivalently whether the polynomial in $(\mathbb Z/q\mathbb Z)[x]$ is invertible modulo $f$.