# Generator for Group $QR_{N}$

Let $N=PQ$, where $P=2p+1$ and $Q=2q+1$. $P,Q,p,q$ are prime numbers. $QR_{N}$ is the set of quadratic residues modulo $N$.

1. Please help me to prove $QR_{N}$ is a cyclic group. Note: $QR_{P}$ and $QR_{Q}$ are cyclic groups.
2. How to find/determine generator for $QR_{N}$?
• Looks like homework. You can find a related answer here. – DrLecter Nov 5 '13 at 6:54
• Hint: what's the size of the group $QR_N$ (that is, how many group members there are)? – poncho Nov 5 '13 at 19:24

Well , I think DrLecter's great answer in here can be used to answer this question indirectly. But as you want to prove so I will give a proof.

To prove $QR_N$ is a cyclic group, first, you have to know the order of it. In fact, the order of $QR_N$ is $pq=\phi(N)/4$($\phi$ is Euler function ).Actually, we can show this with the help of this map:$$x\to (x_P,x_Q)$$ from $Z_N^*$ to $Z_P^* \times Z_Q^*$.Denote $Z_N^* \cong Z_P^* \times Z_Q^*$. It's a one to one map. There is a fact about this map we need to use:

$x$ is quadratic residue if and only if $x_P, x_Q$ are all quadratic residues.

Proof. if $x$ is quadratic residue then there is a $y$ such that $x=y^2 \pmod{N}$. So $x_P, x_Q$ are all quadratic residues. If $x_P, x_Q$ are all quadratic residues, then there are $x_1$, $x_2$, such that $$x_P=x_1^2 \pmod{P}$$ $$x_Q=x_2^2 \pmod{Q}$$ .So we the following equation holds: $$(x_P,x_Q)=(x_1^2,x_2^2)=(x_1,x_2)(x_1,x_2)$$, then using the Chinese remainder theorem, $(x_P,x_Q)$ and $(x_1,x_2)$ point to two elements say $x, y$ in $Z_N^*$. So vice versa.

So with the above fact, we can get $$QR_N \cong QR_P \times QR_Q$$. So $|QR_N|=|QR_P||QR_Q|=\frac{P-1}{2} \frac{Q-1}{2}=pq=\phi(N)/4$.

In order to prove $QR_N$ is a cyclic group, then you must show that this is an element in it that has the order of $pq$. We know that $QR_P$ is subgroup of $Z_P^*$ and 'cause its order is prime $p$, then it must be a cyclic group. So does $QR_Q$. So, we can choose non-identity elements $x_P \in QR_P$ and $x_Q \in QR_Q$, and they must be generator. According to Chinese remainder theorem and the fact above, then $(x_P,x_Q)$ goes to a element in $QR_N$, and its order is $pq$.

Over...