Cardinality of the group of units in a cyclotomic ring? 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&gt;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&gt;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.