2
$\begingroup$

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.

$\endgroup$

1 Answer 1

3
$\begingroup$

$(\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$.
$\endgroup$
3
  • $\begingroup$ 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 ? $\endgroup$
    – skii
    Jan 9, 2018 at 16:15
  • $\begingroup$ @Akanksha Dixit: yes; hopefully that's clarified. $\endgroup$
    – fgrieu
    Jan 9, 2018 at 16:47
  • $\begingroup$ oh yes. comment was updated a little late here. thanks. $\endgroup$
    – skii
    Jan 9, 2018 at 17:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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