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?


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.