How to find all natural $x$ that make $x^{15} \equiv -1 \mod p$, where $p$ is prime and xFor a given prime $p$, how do I find all natural $x$ that make $x^{15} \equiv -1 \mod p$, where $p$ is prime and x < p? The problem is that trying thoroughly every $x < p$ is too inefficient. I am aware of algorithms like Tonelli-Shanks that give result for squares, but how do I generalize it to other powers?
Sorry for involving some CS! 
 A: Since you want to solve $x^n \equiv -1\pmod{p}$ with an odd $n$, the problem is accessible. Since $n$ is odd, we have $x^n \equiv -1\pmod{p}\iff (p-x)^n \equiv 1 \pmod{p}$, so it suffices to solve the marginally simpler problem $y^n \equiv 1 \pmod{p}$. The set of solutions of this problem has the nice property that is is a (cyclic) subgroup of the group of units modulo $p$.
If $n$ is not a divisor of the order of the group of units modulo $p$ (that is, if $n \nmid p-1$), consider $m = \gcd (n, p-1)$, then you have $y^n \equiv 1 \pmod{p} \iff y^m \equiv 1\pmod{p}$, so I will assume that $n\mid p-1$. Then $G = \{ y : y^n \equiv 1 \pmod{p}\}$ is a subgroup of order $n$ of $\left(\mathbb{Z}/(p)\right)^\times$, and for every $a \in\left(\mathbb{Z}/(p)\right)^\times$, we have $a^{(p-1)/n}\in G$.
So the basic strategy is to look at $a^{(p-1)/n}$ until you have a set of $n$ distinct solutions. At the beginning, we know $1\in G$. You can either look at $a = 2,3,4,\dotsc$ in sequence, or draw $a \in \{ 2,3,\, \dotsc,\, (p-1)/2\}$ (pseudo-)randomly, and for each $a$ compute $r_a = a^{(p-1)/n}\bmod{p}$.
If $r_a$ is among the already known solutions, you get nothing new and proceed to the next base. Otherwise, consider the powers $r_a^1, \, r_a^2,\, \dotsc\, r_a^k = 1$, where $k$ is minimal with $r_a^k \equiv 1\pmod{p}$. If all previously known solutions are among the $r_a^m$, then you know nothing more than the $k$ solutions generated by $r_a$, but if the generator $y_1$ of the previously known solution set is not among the $r_a^m$, you get more solutions of the form $y_1^j\cdot r_a^m$, altogether $\operatorname{lcm}(k,s)$ solutions, where $s$ is the number of previously known solutions, the order of $y_1$ modulo $p$.
I can't name an algorithmic complexity for the method, and if you're extremely unlucky, it will be slow, but ordinarily, it should be reasonably fast. For $n = 15$, the probability that $a^n$ does not generate $G$ (for a randomly with uniform probability chosen $a$), the probability that $a$ is a third or fifth power, is $\frac13 + \frac15 - \frac{1}{15} = \frac{7}{15} < \frac12$, so you should hit a generator of $G$ after a few (two or three, maybe four) trials when drawing $a$ randomly.
