3
$\begingroup$

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}$?
$\endgroup$
2
  • $\begingroup$ Looks like homework. You can find a related answer here. $\endgroup$
    – DrLecter
    Commented Nov 5, 2013 at 6:54
  • $\begingroup$ Hint: what's the size of the group $QR_N$ (that is, how many group members there are)? $\endgroup$
    – poncho
    Commented Nov 5, 2013 at 19:24

1 Answer 1

2
$\begingroup$

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

P.S. Although, i answer your question, but i agree with DrLecter, it likes like your homework, you should think about it yourself.

$\endgroup$

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.