Number theory in Cryptography: Can I say two following subgroups are isomorphic?

Question

I am a cryptographer. for designing an encryption system, I need some number theory/algebraic conditions to be satisfied. So I know what I need, but I dont know if they are really satisfied in the algebraic point of view or not.

Here is a short description: I have an integer $n=pq$ where $p=2p'+1$ and $q=2q'+1$ and $p,q,p',q'$ are primes. Group $\mathbb{Z}_n^*$ is multiplicative group modulo $n$ (i.e including all invertiable elements $a\in \mathbb{Z}_n$). We say that $class_n[k]$ is a the class of $k$ residues of $\mathbb{Z}_n^*$, if $class_n[k]=\{g^{k} ~\text{mod}~ n~:~ g\in \mathbb{Z}_{n}^*\}$.

Now consider that $QR=class_n[2]$ is the subgroup of quadratic residues of $\mathbb{Z}_n^*$, and $Class_{n^2}[2n]$ is the subgroup of $2n$ residues of $\mathbb{Z}_{n^2}^*$. i.e., $class_{n^2}[2n]=\{g^{2n}~ \text{mod}~ n^2~:~ g\in \mathbb{Z}_{n^2}^*\}$.

If the answers to the following questions are positive, it will make me happy!

1) Can I say that this two subgroups $class_n[2]$ and $class_{n^2}[2n]$(respectively, of $\mathbb{Z}_n^*$ and $\mathbb{Z}_{n^2}^*$) are isomorphic?

2) Can I say $|class_{n^2}[2n]|=\lambda(n^2)/2n$ ? where $|\cdot |$ is the order of the group and $\lambda(.)$ is the Carmichael function.

Answer 1

The first claim does not hold in general. A potential problem is the possibility that $p=q'$.

Remember that in a cyclic group $C_m$ raising to power $\ell$ is a homomorphism with a kernel of size $\gcd(\ell,m)$, and hence an image of order $m/\gcd(m,\ell)$.

Consider the example case of $p=11=q'$, $q=23$.

• By the Chinese remainder theorem $\Bbb{Z}_{pq}^*\simeq C_{10}\times C_{22}$. We see that squaring has a kernel of order four, and there will $22\cdot10/4=55$ quadratic residues modulo $n=pq=253$.
• But, again by the Chinese remainder theorem, $$\Bbb{Z}_{p^2q^2}^*\simeq C_{p(p-1)}\times C_{q(q-1)}=C_{2\cdot5\cdot11}\times C_{2\cdot11\cdot23}.$$Raising to power $2n=2\cdot11\cdot23$ therefore annihilates the latter factor completely, and there will be only $5$ distinct $2n$th power residues modulo $11^2\cdot23^2$. All of them will be congruent to $1$ modulo $23^2$.

I have not checked, but this may well be the only obstacle. At least it looks like adding the assumption that $p',q',p,q$ should all be distinct primes would make the above problem go away. Because the resulting group is abelian of order $p'q'$, it is necessarily cyclic, and therefore the two groups in 1) should be isomorphic.