Cube roots modulo $p$ Let $a$ be a positive integer.
Is there any general method of solving equations of the form 
$$x^3\equiv a$$ 
modulo $p$, where $p$ is a prime number?
Here are two examples:
Example 1: In $\mathbb{Z}_{13}^*$ (using multiplication as our binary operation) we have that $x^3=7$ has no solutions, since $(x^3)^4=7^4$ is equivalent to $x^{12}=1=7^4$; by Fermat's little theorem $x^{12}=x^{13-1}=1$ modulo $13$, but $1\neq 7^4$ in $\mathbb{Z}_{13}^*$.
Example 2: In $\mathbb{Z}_{19}^*$ we have, by trial and error, that $4$, $6$ and $9$ solves the equation $x^3=7$. 
Is there any general way of solving such equations? For example: how would I solve the same problem, $x^3\equiv 7$, but modulo $p=41$? 
 A: See this article, http://eprint.iacr.org/2013/024.pdf , for an extension of Tonelli-Shanks to the discrete cube root problem.  It claims a running time proportional to that of exponentiation in $\mathbf{F}_p$.
A: Very complex responses (in an old post) .... If you are familiar with RSA public key cryptosystem
$m^e\equiv c    (\bmod n)$    encryption
$c^d\equiv m    (\bmod n)$    decryption
$e\cdot d \equiv 1 (\bmod ~\varphi(n))$
look at what happens when you set $e = 3$ : the decryption equation is exactly the problem you are trying to solve when starting from the encryption operation.



you can compute d as $d \equiv {1 \over e} \bmod ~\varphi(n)$ but this is rather unusual as $~\varphi(n))$ is even and an even moduli require a little bit more of cautious operation. Could use Hensel lifting and CRT in the general case. To make it simple, from this variant of Bezout formula,


$e({1 \over e} \bmod ~\varphi(n)) + ~\varphi(n)( {1 \over {\varphi(n)}} \bmod e)$ = $1 + e ~\varphi(n)$


let $b = {1 \over \varphi(n)} \bmod e$


this can be rewritten as 


$d = {1 \over e} \bmod ~\varphi(n) = {1 + \varphi(n)(e - b) \over e}$


This is a general solution which works for any modulus n and exponent e as long as  $gcd(e, ~\varphi(n)) \equiv 1$



To answer your question $\bmod n=41$


step 1 : solve $b = {1 \over 40}  \bmod 3$  using the binary extended euclidean algorithm
i.e. b = 1


step 2 : compute $d = {1 \over 3} \bmod 40$ as $(1 + 40(3 - b))/3$
i.e. d = 81/3 = 27


finally $a\equiv x^3 (\bmod 41)$ is equivalent to $x\equiv a^{27} (\bmod 41)$
CQFD


Note that this is consistent with an earlier response which mention that there is only one single cube root when $n \equiv 2(\bmod 3)$



When the modulus is not a prime (a requirement for RSA cryptosystem strength, but not for a cubic root), you can extend this calculation to the case  of RSA when n has two and more known factors (aka RSA multiprime and its abundant literature). 
