# How to select elements randomly from a multiplicative group Zn*

I am working on a problem in which I have two large safe primes say p and q randomly selected each of 512 bits. I have generated these safe primes using OpenSSL library.Now,

n = pq

What will be Zn* called? Is it a group under multiplication modulo n and same as (Z/nZ)*? But I have read that (Zn,⋅), integers modulo n under multiplication, is a group if and only if n is prime? In this link

What all comprises the elements of this group if at all this is a group? And is there way to select its elements randomly using a code in C/C++ using some library like Openssl.

Thanks and Regards.

$(\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$.
• in the heuristic method you propose to generate a random integer, did you mean (0,n] here? Also x in this construction is refering to the interger generated ? – skii Jan 9 '18 at 16:15
• @Akanksha Dixit: yes; hopefully that's clarified. – fgrieu Jan 9 '18 at 16:47
• oh yes. comment was updated a little late here. thanks. – skii Jan 9 '18 at 17:40