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$?

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.