Higher Residuosity Problem - Mathematical Background

Mathematical Background

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

The group of units of any ring form a group, and the group of units in is traditionally denoted .

From the isomorphism above, we have

as an isomorphism of groups. Since p and q were assumed to be prime, the groups and are cyclic of orders p-1 and q-1 respectively. If d is a divisor of p-1, then the set of dth powers in form a subgroup of index d. If gcd(d,q-1) = 1, then every element in is a dth power, so the set of dth powers in is also a subgroup of index d. In general, if gcd(d,q-1) = g, then there are (q-1)/(g) dth powers in, so the set of dth powers in 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 are quadratic residues (when n is the product of exactly two primes, as it is here).

The important point is that for any divisor d of p-1 (or q-1) the set of dth powers forms a subgroup of