Let $p$ and $q$ are Sophie-Germain primes such that $p=2p'+1$ and $q=2q'+1$. Also let $n=pq$ and $n'=p'q'$. In Section 8.2.1 of this paper, the internal direct product of $\mathbb{Z}_{n^2}^*$ is shown as $$\mathbb{G}_{n}\cdot\mathbb{G}_{n'}\cdot\mathbb{G}_{2}\cdot T$$ where $\mathbb{G}_{\tau}$ is the cyclic group with the order $\tau$ and $T$ is the subgroup generated by $-1\text{ mod }n^2$. Furthermore, the paper says that this decomposition is unique except $\mathbb{G}_{2}$ where there are two possible choices. However, as far as I know, there is a unique cyclic group with order 2. Hence, I think that $\mathbb{G}_{2}$ must also be unique. What am I missing there?


1 Answer 1


Let $g$ be such that $g\equiv 1\pmod {p^2}$ and $g\equiv -1\pmod {q^2}$, there is a unique solution to this by the Chinese remainder theorem (and this solution is not 0, 1 or -1). We see that $\langle g\rangle$ is a cyclic group of order 2, because $g^2\equiv 1\pmod {p^2}$ and $g^2\equiv 1\pmod {q^2}$ which implies that $g^2\equiv 1\pmod {n^2}$.

Likewise let $h$ be such that $h\equiv -1\pmod {p^2}$ and $h\equiv 1\pmod {q^2}$, there is a unique solution to this by the Chinese remainder theorem. We see that $\langle h\rangle$ is also a cyclic group of order 2, but the groups are distinct.

Note that $g=-h$ and vice-versa.

The group $\mathbb G_2$ can be taken as either $\langle g\rangle$ or $\langle h\rangle$.

  • $\begingroup$ Let me ask a further question which is both related to the paper and the previous question. Let $g'\leftarrow \mathbb{Z}_{n^2}^*$ and $g=(g')^{2n}$. Then, considering our direct product, $g$ must be a member of $\mathbb{G}_{n'}$, right? $\endgroup$
    – kentakenta
    Feb 13, 2022 at 14:13
  • 1
    $\begingroup$ Yes (assuming that you've not picked a pathological case such as $p'=q$). $\endgroup$
    – Daniel S
    Feb 13, 2022 at 14:34

Your Answer

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

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