# What is the restriction on $k$, for the $k$th composite residuosity problem to be hard?

The paper “Residuosity Problem and Its Applications to Cryptography” considers the exponent to be an odd integer.

When $k = 2$, it is called the quadratic residuosity problem (mod $n$, where $n$ is composite) which is hard and can be solved if the factorization of n is known.

What happens to the $k$th residuosity problem if $k$ is an even integer $> 2$?

• If the factorization of $n$ is known, the higher residuosity problem modulo $n$ can be easily solved. The other direction is unknown. – user94293 May 29 '16 at 3:33
• You may take a look at dx.doi.org/10.1007/s00145-016-9229-5 when $k$ is a power of $2$. – user94293 May 29 '16 at 3:38