Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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}$?
share|improve this question
    
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

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.