Suppose we are given an integer $ c$ and positive integers $ k, N$ , with no further assumptions on relationships between these numbers. We are also given the prime factorization of $ N$ . These inputs are written in binary. What is the best known time complexity for determining whether there exists an integer $ x$ such that $ x^k \equiv c \pmod{N}$ ?

We are given the prime factorization of $ N$ because this problem is thought to be hard on classical computers even for *k* = 2 if we do not know the factorization of $ N$ .

This question was inspired by this answer, where D.W. stated that the nonexistence of a solution to $ x^3 \equiv 5 \pmod{7}$ can be checked by computing the modular exponentiation for $ x = 0,1,2,3,4,5,6$ , but that if the exponent had been 2 instead of 3, we could have used quadratic reciprocity instead. This lead to my discovery that there are a large number of other reciprocity laws, such as *cubic reciprocity*, *quartic reciprocity*, *octic reciprocity*, etc. with their own Wikipedia pages.