Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
In the NTRU key generation, one samples a polynomial from $K = (\mathbb Z/q\mathbb Z)[X]/(X^n+1)$ and tests if it is invertible. What are the chances of this to happen? In other words:
Let $q$ be a prime and $n>4$ be a power of $2$. What is the cardinality of $K^*$?
The $n$th cyclotomic polynomial $\Phi_n\in\mathbb Z[x]$ is irreducible in $\mathbb F_q[x]$ if and only if $q$ is a generator of $(\mathbb Z/n)^\times$ (proof). Hence, unfortunately, the polynomial $x^n+1$ is never irreducible modulo $q$ if $n>4$ is a power of two: The group $(\mathbb Z/n)^\times$ is not cyclic in that case. Thus it may indeed happen that the polynomial chosen in NTRU is not invertible.
Since I am not aware of any exact results, we shall derive a generic lower bound for the cardinality of $(\mathbb F_q[x]/(x^n+1))^\times$. (By "generic", I mean that the following is not specific to cyclotomic polynomials. I suspect one can obtain much better bounds by using cyclotomic theory.)
I will assume $q\geq3$. Then the polynomial $x^n+1$ is square-free over $\mathbb F_q$ since $\gcd(x^n+1,nx^{n-1})=1$. Decompose $x^n+1$ into (therefore distinct) irreducible factors $g_i\in\mathbb F_q[x]$ of degrees $e_i:=\deg g_i$. By the Chinese remainder theorem, we have an isomorphism $$ \varphi\colon\quad \mathbb F_q[x]/(x^n+1) \;\cong\; \prod_{i=1}^r\underbrace{\mathbb F_q[x]/g_i}_{\cong\ \mathbb F_{q^{e_i}}} \text. $$ Composing this isomorphism with projections to the direct factors $\mathbb F_q[x]/g_i$ yields ring homomorphisms $$ \pi_i\colon\quad \mathbb F_q[x]/(x^n+1) \;\to\; \mathbb F_{q^{e_i}} $$ with the property that an element of $\mathbb F_q[x]/(x^n+1)$ is invertible if and only if its image under each $\pi_i$ is invertible, i.e., non-zero. Hence the probability that an element $f\in\mathbb F_q[x]/(x^n+1)$ chosen uniformly at random is a unit is $$ \Pr[\text{unit}] \;=\; \prod_{i=1}^r (1-1/q^{e_i}) \text. $$ How bad can this become? In the worst case, we have $r=n$ and all $e_i=1$, hence $$ \Pr[\text{unit}] \;\geq\; (1-1/q)^n \text. $$
When considering small $q$ and large $n$, this bound becomes quite low quickly, but keep in mind that it is a worst-case estimate. In practice, it seems that the $e_i$ are typically much greater than $1$.
Moreover, in the NTRU scenario, $q$ is quite big: The parameters recommended, depending on the source, are roughly $q\approx 2000$ and $n\approx 1000$, yielding $$ \Pr[\text{unit}] \;\geq\; \frac12 \text, $$ so one can easily find a unit within a few tries with very large probability.
This depends on the factorization of $X^n+1$ modulo $\mathbb{F}_q$.
If you have $X^n+1 = \prod_i f_i(X)^{e_i}$ with $f_i$ irreducible and $e_i>0$, then $K = \prod_i \mathbb{F}_q[X]/(f_i^{e_i})$ and $K^\times = \prod_i (\mathbb{F}_q[X]/(f_i^{e_i}))^\times$.
An element of $\mathbb{F}_q[X]/(f_i^{e_i})$ is invertible, iff it is invertible modulo $f_i[X]$. As $\mathbb{F}_q[X]/(f_i)$ is a field of order $q^{\deg f_i}$, you should get $|K^\times|/|K| = \prod_i (1-q^{-\deg f_i})$.
