Higher residuosity problem
In cryptography, most public key cryptosystems are founded on problems that are believed to be intractable. The higher residuosity problem (also called the n th-residuosity problem) is one such problem. This problem is "easier" to solve than integer factorization, so the assumption that this problem is hard to solve is "stronger" than the assumption that integer factorization is hard. 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 formula_2 is traditionally denoted formula_3. From the isomorphism above, we have as an isomorphism of "groups". Since "p" and "q" were assumed to be prime, the groups formula_5 and formula_6 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 formula_5 form a subgroup of index "d". If gcd("d","q"-1) = 1, then "every" element in formula_6 is a "d"th power, so the set of "d"th powers in formula_9 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 formula_6, so the set of "d"th powers in formula_9 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 formula_9 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 "d"th powers forms a subgroup of formula_13 Problem statement. 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 When "d"=2, this is called the quadratic residuosity problem. Applications. The semantic security of the Benaloh cryptosystem and the Naccache–Stern cryptosystem rests on the intractability of this problem. Higher residuosity problem