2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

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

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.