Group of quadratic residues modulo n

From CRYPTUTOR

The set $\mathbb{QR}^*_n=\{x \in \mathbb{Z}^*_n \,|\, \exists q \in \mathbb{Z}^*_n, ~ q^2 \equiv x ~ ({\rm mod}~n) \}$ forms an abelian group under multiplication modulo $n$ , with 1 representing the identity element. We call this group the group of quadratic residues modulo $n$ . It is a subgroup of the multiplicative group $\mathbb{Z}^*_n$ .

When $n$ is an odd prime, $\mathbb{QR}^*_n$ has $(n-1)/2\,$ elements and is a cyclic group. Also, for each $x \in \mathbb{QR}^*_n$ , the value $q$ in the above definition is unique within $\mathbb{QR}^*_n$ , and called $\sqrt{x}$ . Further, when $n$ is a safe prime, $\mathbb{QR}^*_n$ is a group with prime order, and the Decisional Diffie-Hellman assumption is believed to hold in the group.

When $n$ is a product of two primes $p$ and $q$ , $\mathbb{QR}^*_n$ is isomorphic to the product group $\mathbb{QR}^*_p \times \mathbb{QR}^*_q$ .

Retrieved from "http://crypto.cs.uiuc.edu/wiki/index.php/Group_of_quadratic_residues_modulo_n"

Group of quadratic residues modulo n

From CRYPTUTOR

Views

Personal tools

Navigation

Search

Toolbox