# 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...