2
$\begingroup$

Let N = pq be one publicly known RSA modulus, in which p = 2p′ + 1, q = 2q′ + 1 are two large primes. p′ and q′ are also primes. All the quadratic residues modulo N forms a multiplicative cyclic group of order p′q′. My question is , how is this order computed?

Thank you for your attention!

  • 0
    Related to http://math.stackexchange.com/questions/30800/when-is-the-group-of-quadratic-residues-cyclic2012-05-15

1 Answers 1

3

We have $U_N \cong U_p \times U_q$. By Euler's criterion, the quadratic residues mod a prime $t$ form a subgroup of $U_t$ of index 2 . Hence the quadratic residues mod $N$ form a subgroup $R$ of index 4. Now $|U_N| = (p-1)(q-1) = 4p'q'$ and so $|R|=p'q'$.

Finally, $U_N \cong U_p \times U_q \cong C_{p-1} \times C_{q-1} = C_{2p'} \times C_{2q'} \cong C_2 \times C_2 \times C_{p'q'}$, which shows that $R \cong C_{p'q'}$ is cyclic, as that is the only subgroup of index 4.