If n is an integer, then the integers modulo n form a ring. If n = pq where p and q are primes, then the Chinese remainder theorem tells us that

${\displaystyle \mathbb {Z} /n\mathbb {Z} \simeq \mathbb {Z} /p\mathbb {Z} \times \mathbb {Z} /q\mathbb {Z} }$ 

The units of any ring form a group under multiplication, and the group of units in ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$  is traditionally denoted ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$ .

From the ring isomorphism above, we have

${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }\simeq (\mathbb {Z} /p\mathbb {Z} )^{\times }\times (\mathbb {Z} /q\mathbb {Z} )^{\times }}$ 

as an isomorphism of groups. Since p and q were assumed to be prime, the groups ${\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{\times }}$  and ${\displaystyle (\mathbb {Z} /q\mathbb {Z} )^{\times }}$  are cyclic of orders p−1 and q−1 respectively. If d is a divisor of p−1, then the set of d th powers in ${\displaystyle (\mathbb {Z} /p\mathbb {Z} )^{*}}$  form a subgroup of index d. If gcd(d,q−1) = 1, then every element in ${\displaystyle (\mathbb {Z} /q\mathbb {Z} )^{\times }}$  is a d th power, so the set of d th powers in ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$  is also a subgroup of index d. In general, if gcd(d,q−1) = g, then there are (q−1)/g d th powers in ${\displaystyle (\mathbb {Z} /q\mathbb {Z} )^{\times }}$ , so the set of d th powers in ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$  has index dg. This is most commonly seen when d = 2, and we are considering the subgroup of quadratic residues, it is well-known that exactly one quarter of the elements in ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$  are quadratic residues (when n is the product of two primes, as it is here).

The important point is that for any divisor d of p−1 (or q−1) the set of d th powers forms a subgroup of ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }.}$ 

Given an integer n = pq where p and q are unknown, an integer d such that d divides p−1, and an integer x < n, it is infeasible to determine whether x is a d th power (equivalently d th residue) modulo n.

Notice that if p and q are known it is easy to determine whether x is a d th residue modulo n because x will be a d th residue modulo p if and only if

${\displaystyle x^{(p-1)/d}\equiv 1{\pmod {p}}}$ 

When d = 2, this is called the quadratic residuosity problem.

The semantic security of the Benaloh cryptosystem and the Naccache–Stern cryptosystem rests on the intractability of this problem.