# What is the time complexity of determining whether a solution $x$ exists to $x^k \equiv c \pmod{N}$ if we know the factorization of $N$?

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.

If $$p$$ is prime, then $$x^k\equiv c \pmod p$$ has a solution if and only if $$c^{(p-1)/g} \equiv 1$$ where $$g=\gcd(k,p-1)$$. The solution is given by $$x \equiv \sqrt[g]{c^h} \pmod p$$ where $$h^{-1} \equiv k/g \pmod{p-1}$$. You can take $$g$$th roots in polynomial time using an extension of the Tonelli-Shanks algorithm; see On taking roots in Finite Fields by Adleman, Manders, and Miller. (Strictly speaking, this algorithm requires either reasonable number theoretic assumptions or randomization.) Given one solution $$x$$, the other solutions will have the form $$x \beta^i$$ where $$\beta$$ is an element of order $$g$$ modulo $$p$$.

If $$p^m$$ is a prime power and $$\gcd(p,k)=1$$, then you can use Hensel lifting to test whether $$x^k \equiv c \pmod{p^m}$$ has a solution. In particular, let $$x_i=x \bmod p^i$$ and $$c_i=c \bmod p^i$$ and $$y_i = (x_{i+1} - x_i)/p$$ and $$d_i = (c_{i+1} - c_i)/p$$. Now find $$x_1$$ such that $$x_1^k \equiv c_1 \pmod p$$. If this has no solution, then neither does $$x^k \equiv c \pmod{p^m}$$, so we can terminate immediately. Otherwise, we're next going to try to find $$x_2$$ such that $$x_2^k \equiv c_2 \pmod{p^2}$$. Writing $$x_2 = x_1 + p y_1$$ and $$c_2 = c_1 + p d_1$$, we obtain the equation

$$(x_1 + y_1 p)^k \equiv (c_1 + d_1 p) \pmod{p^2},$$

or equivalently,

$$k x_1 y_1 \equiv (c_1 - x_1^k)/p + d_1 \pmod p.$$

If $$k x_1 \not\equiv 0 \pmod p$$, then we can let $$y_1 = ((c_1 - x_1^k)/p + d_1) \cdot (k x_1)^{-1} \bmod p$$ and we have a solution for $$x_2$$. Otherwise, test whether $$x_1^k \equiv c_2 \pmod{p^2}$$; if it is, then setting $$x_2=x_1$$ gives a solution, otherwise there is no solution and we can terminate. Repeat the same process to find $$x_3$$, then $$x_4$$, etc., until you have found $$x_m$$. While there may be multiple possible solutions for $$x_1$$, there is no need to branch and try all of them, because either all will be extendable to $$x_m$$ or none will.

I am not sure what to do if $$\gcd(p,k)=1$$. Perhaps someone else can fill in this gap.

If $$N$$ is a product of prime powers $$p_1^{m_1} \cdots p_n^{m_n}$$, then you can use the Chinese remainder theorem to check for a root modulo each of the $$p_j^{m_j}$$. A root exists modulo $$N$$ if and only if it exists modulo each prime power; and once you've found a solution for each prime power, you can combine them with the CRT to obtain a solution modulo $$N$$.

Proof for first paragraph: If $$p$$ is prime, then there exists an element $$\alpha$$ of order $$p-1$$; assuming $$x \equiv \alpha^X \pmod p$$ and $$c \equiv \alpha^C \pmod p$$, we find that the equation has a solution if and only if $$Xk \equiv C \pmod{p-1}$$ has a solution, which is equivalent to the stated condition in the first paragraph.

• That's a pretty nice pile of number theory for an answer that doesn't even cover all the cases! 😃 Dec 15 '19 at 19:16