Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Is there an efficient way (algorihtm) to compute the solutions of the congruence $x^n\equiv a \pmod p$?

  • $n\in \mathbb{N}$

  • $a\in\mathbb{Z}_p$

  • $p$ is a large prime number

Note that:

  • By efficient I mean computationally efficient even when the given prime $p$ is appropriate for use in cryptographic protocols (hard to find discrete logarithm in $\mathbb{Z}_p$)

  • We do not know the prime factors of $p-1$.

It’s easy to find one solution when $\gcd(n,p-1)=1$.

I think this should be as hard as finding a Discrete Logarithm or as Factoring. Any ideas ? Thank you for your time.

share|improve this question
add comment

3 Answers 3

up vote 7 down vote accepted

This is an extended but still partial attempt at an explicit solution.

Since $p$ is prime, Fermat's little theorem tells us that:

  • $\forall z\in\mathbb Z_p, z^p\equiv z\pmod p$.
  • $\forall z\in\mathbb Z_p^*, z^{p-1}\equiv1\pmod p$.

We settle some easy cases:

  • If $n=0$ and $a\equiv 0\pmod p$, our equation $x^n\equiv a\pmod p$ is ill-defined.
  • If $n>0$ and $a\equiv 0\pmod p$, the solution is $x\equiv0\pmod p$.
  • If $n\equiv0\pmod{p-1}$ and $a\equiv 1\pmod p$, any $x\not\equiv0\pmod p$ is solution.
  • If $n\equiv0\pmod{p-1}$, $a\not\equiv 0\pmod p$ and $a\not\equiv 1\pmod p$, there is no solution.
  • If $n\equiv1\pmod{p-1}$, the solution is $x\equiv a\bmod p$.

In all the other cases, $x\equiv0\pmod p$ will not be a solution, and we can reduce $n$ modulo $p-1$ to obtain an equivalent equation. From then on, we will assume $1<n<p-1$, $a\not\equiv0\pmod p$, $x\not\equiv0\pmod p$, and proceed to solve our equation $x^n\equiv a\pmod p$.

As pointed out in the question, things are easy when $\gcd(n,p-1)=1$: the only solution is $x\equiv a^{n^{-1}\bmod(p-1)}\pmod p$. Proof: For the stated $x$, we have $x^n\equiv a^{(n^{-1}\bmod(p-1))·n}\pmod p$; thus $\exists k\in\mathbb N, x^n\equiv a^{1+k·(p-1)}\pmod p$; thus $x^n\equiv a\pmod p$; thus the stated $x$ is a solution of our equation. The function $z\mapsto z^n$ is thus a surjective function over the finite set $\mathbb Z_p^*$, thus a bijection, thus there is no solution other than the stated one.

If $\gcd(n,p-1)\neq 1$, let it be $m$, with both $n/m$ and $(p-1)/m$ integers. We find $b$ such that $b^{n/m}\equiv a\bmod(p-1)$ by the above method; that is: $b=a^{(n/m)^{-1}\bmod(p-1)}\bmod p$. Solving $x^m\equiv b\pmod p$ is equivalent to our original equation.

By raising to the power $(p-1)/m$, we see that $x^m\equiv b\pmod p\implies 1\equiv b^{(p-1)/m}\pmod p$. Thus if $1\not\equiv b^{(p-1)/m}\pmod p$, which we can check, there is no solution.

This test is quite useful; for example when $p=71$, $n=55$, $a=2$, we have $m=5$, $(n/m)^{-1}\bmod(p-1)=51$, $b=3$, $b^{(p-1)/m}\bmod p=54$, thus no solution, and that's the case for most $a$. But for $a=20$ we get $b=45$, $b^{(p-1)/m}\bmod p=1$, and indeed there are $5$ solutions $\{18,19,24,32,49\}\pmod p$.


We can thus restrict to solving $x^n\equiv a\pmod p$ when $n$ divides $p-1$, $n>1$, and $a^{(p-1)/n}\equiv 1\pmod p$ (we have shown that any other $a$ leaves the equation without solution, except $a\equiv 0\pmod p$; and we have an efficient method to reduce to that case for any other $n$).

That equation has exactly $n$ distinct solutions $\pmod p$. Proof: by the fundamental theorem of algebra, any polynomial of degree $n$ in the field $\mathbb Z_p$ has exactly $n$ roots, counted with multiplicity; applying that to $x^n-a$ we see that $x^n\equiv a\pmod p$ has at most $n$ solutions $\pmod p$; similarly there are at most $(p-1)/n$ solutions in $a$ to the equation $a^{(p-1)/n}\equiv 1\pmod p$; thus the function $z\mapsto z^n$ over the finite set $\mathbb Z_p^*$ maps at most $n$ elements to any element, and at most $(p-1)/n$ elements have a preimage; by a counting argument, every element with a preimage thus has exactly $n$ preimages.

It follows that we can not aim at finding all the solutions in time polynomial w.r.t. $\log p$ for arbitrary $n$: there are too many solutions when $n$ is big, e.g. $n=(p-1)/2$. We can still aim at finding one solution, or perhaps the smallest one.

When $(p-1)/n$ is small, there is an efficient and trivial probabilistic algorithm that finds a solution: pick a random $x$, and check if $x^n\equiv a\pmod p$, until a suitable $x$ is found; that is expected to require $(p-1)/n$ steps. By trying $x$ sequentially starting from $2$, we can find the smallest $x$.

If the exponent $n$ is even, we can change the unknown to $y\equiv x^{n/2}\pmod p$ and first solve $y^2=a\pmod p$, which is the well-studied problem of finding a square root modulo a prime. By applying this recursively, we can remove the powers of $2$ from the factorization of $n$. Assuming a polynomial-time algorithm finding a solution for any odd exponent $n$, our resulting algorithm would find a solution and work for any exponent, while remaining polynomial in $\log p$ after reduction of the exponent $n\pmod p$.

This is studied and generalized by Adleman-Manders-Miller, solving the problem in time polynomial w.r.t. $\log p$ for fixed $n$. Their algorithm is (at worse) linear w.r.t. $n$ (not $\log n$), and as an aside requires the factorization of $n$.

This might be improved by Barreto-Voloch, and perhaps these two re-visitations of Adleman-Manders-Miller and Barreto-Voloch.

[To be continued. Feel free to improve this community wiki, e.g. by including a description of Adleman-Manders-Miller; I'll have no time to do that in the following week.]

An instance of the original problem with random exponent has a fair chance of being solvable with the above techniques. I have the feeling do not know if this is easier than discrete logarithm modulo $p$ even in the harder cases, like $n\cdot k=(p-1)$ with $k\approx\sqrt{p-1}$, and $p$,$k$,$n$ are primes.

share|improve this answer
    
Thank you for helping out. –  epsilon Feb 28 '13 at 20:56
add comment

There are standard algorithms for this. See, e.g., Section 7.3 of Algorithmic Number Theory (Eric Bach, Jeffrey Shallit, MIT Press, 1996).

If you want to take square roots, you can use Cipolla's algorithm, the Tonelli-Shanks algorithm, or Pocklington's algorithm. The Tonelli-Shanks algorithm apparently has a generalization to take arbitrary $n$th roots.

The GAP software can take $n$th roots modulo a prime (see RootMod).

Here are some academic papers that also describe algorithms for solving this problem:

These algorithms are computationally efficient if $n$ is small.

I don't know if there are any algorithms that are computationally efficient if $n$ is large (i.e., that work for arbitrary $n$). It's a good question!

share|improve this answer
    
Do you know the asymptotic cost of these algorithms w.r.t. to the exponent, in the worst case? –  fgrieu Mar 2 '13 at 10:45
    
@fgrieu, good question. Actually, now that I take another look at those two papers, the running time seems to be linear in $n$, whereas we'd really want a running time that is poly($\log n$). I don't know whether there are efficient algorithms for large $n$. –  D.W. Mar 2 '13 at 11:02
add comment

Yes, there is. There is a polynomial algorithm for solving general polynomial equations, like $x^n - a \mod{p}$ in a finite field. And for simple powers, its even easier. So I wouldn't use this for a crypto system. Note that even square roots modulo a composite number is hard.

share|improve this answer
    
Can you be more precise? I couldn’t find an efficient algorithm to compute roots in $\mathbb{Z}_p$ if computing discrete logarithms there is hard. –  epsilon Feb 28 '13 at 18:51
    
@fgrieu: Sorry for the late response and thank you again. If you’re referring to this (a new version) arxiv.org/pdf/1111.4877.pdf (although I haven’t thoroughly read it) see for example that in pg7 last line you’ll have to compute a discrete algorithm or pg8 step 4 of the algorithm which in our case is infeasible. –  epsilon Mar 1 '13 at 7:21
    
In the question as I read it, it is wanted an algorithm polynomial in $\log p$ and $\log n$. Is that the case for the unstated "polynomial algorithm for solving general polynomial equations" you are thinking of? I'm afraid that the algorithm outlined in section 4 here might be polynomial in $n⋅\log p$. Indeed, for simple powers, there are faster options, like Adleman-Manders-Miller but that seems polynomial in $\log p$ for fixed $n$ (notice the step "we factor gcd(n,p−1)"). –  fgrieu Mar 1 '13 at 8:51
1  
Cantor-Zassenhaus or Berlekamp algorithms will factor polynomials, e.g. –  Henno Brandsma Mar 1 '13 at 13:50
1  
Both algorithms have cost polynomial w.r.t. $\log p$, but at least polynomial w.r.t. $n$ (not $\log n$). In the context of the question, we'd like an algorithm polynomial w.r.t. $n$, if there is one (that's to find one solution; enumerating all the solutions has cost at least linear with the number of solutions, which can be $n$). –  fgrieu Mar 2 '13 at 18:05
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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