# Internal direct product of group of invertible elements in a Paillier modulus

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?

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$$.
• 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? Feb 13, 2022 at 14:13
• Yes (assuming that you've not picked a pathological case such as $p'=q$). Feb 13, 2022 at 14:34