$(\mathbb Z_n,+,\cdot)$ and $(\mathbb Z/n\mathbb Z,+,\cdot)$ both denote the ring of integers under addition and multiplication modulo $n$, per perhaps different but in the end equivalent constructions. This set has $n$ elements.
$\mathbb Z_n^*$ and $(\mathbb Z/n\mathbb Z)^*$ both denote the subset of elements of said set which have an inverse under multiplication modulo $n$ (or equivalently, which Greatest Common Divisor with $n$ is 1). It forms a group under multiplication modulo $n$.
The ring $(\mathbb Z_n,+,\cdot)$ is a field if and only if $n$ is prime, in which case $\mathbb Z_n^*$ is simply $\mathbb Z_n-\{0\}$.
By definition, $x$ in $\mathbb Z_n$ belongs to $\mathbb Z_n^*$ if and only if $x$ has a multiplicative inverse $y$ , that is such that $x\,y\equiv1\pmod n$ (or equivalently, if and only if $\gcd(x,n)=1$ ). When $n=p\,q$ with $p$ and $q$ primes, this is if and only if $x$ is such that $x\ne0\pmod p$ and $x\ne0\pmod q$ . The set $\mathbb Z_n^*$ has $\varphi(n)$ elements, where $\varphi$ is Euler's totient function. If $p\ne q$ , then $\mathbb Z_n^*$ is the set of the $\varphi(n)=(p-1)(q-1)$ elements of $\mathbb Z_n$ that are divisible by neither $p$ nor $q$ . If $p=q$ , then $\mathbb Z_n^*$ is the set of the $\varphi(n)=p(p-1)$ elements of $\mathbb Z_n$ that are not divisible by $p$ .
We can obtain a uniformly random element of $\mathbb Z_n^*$ in several ways:
- Heuristically: generate a uniformly random integer $x$ in $\mathbb Z_n$ (that is a uniformly random integer in $[0,n)$ ) until $x$ is divisible by neither $p$ nor $q$ (which if almost certain in practice if $p$ and $q$ are large). We can equivalently test if $\gcd(x,n)=1$ using the Euclidean or Binary GCD algorithm, with the advantage that we do not need the factorization of $n$. Also, we can as well generate $x$ in $[1,n)$ before testing it, since we'd eliminate $x=0$ anyway.
- Constructively: generate a uniformly random integer $u$ in $[1,p)$ , and
- if $q\ne p$ generate a uniformly random integer $v$ in $[1,q)$ , and form $x$ in $[0,n)$ with $x\equiv u\pmod p$ and $y\equiv v\pmod q$ by the Chinese Remainder Theorem; for example, as $x=(q^{-1}(u-v)\bmod p)q+v$.
- if $q=p$ generate a uniformly random integer $m$ in $[0,p)$ , and form $x=m\,p+u$.
