Cube roots modulo $p$

http://en.wikipedia.org/wiki/Cantor%E2%80%93Zassenhaus_algorithm with $x^3-a.........................$

Notice that there is one cube root when $p \equiv 2 \pmod 3,$ and either three cube roots or none when $p \equiv 1 \pmod 3.$ For example, $2$ has three cube roots $\pmod p$ when $p = u^2 + 27 v^2$ in integers, otherwise none (for $p \equiv 1 \pmod 3,$ in which case $p = 4 u^2 + 2 u v + 7 v^2$), and $3$ has three cube roots when $p = x^2 + xy + 61 y^2$ in integers, otherwise none when $p = 7 x^2 + 3 x y + 9 y^2.$

So, the first few primes $1 \pmod 3$ for which we can solve $x^3 \equiv 2 \pmod p $ are $$ 31, 43, 109, 127, 157, 223, 229, 277, 283, 307, 397, 433, 439, 457, 499, 601, 643, 691, 727, 733, 739, 811, 919, 997, $$ In these cases there will be three cube roots; for example, the cube roots of $2 \pmod {31}$ are $4,7,20. $

The first few primes $1 \pmod 3$ for which we can solve $x^3 \equiv 3 \pmod p $ are $$ 61, 67, 73, 103, 151, 193, 271, 307, 367, 439, 499, 523, 547, 577, 613, 619, 643, 661, 727, 757, 787, 853, 919, 967, 991, 997, $$ In these cases there will be three cube roots; for example, the cube roots of $3 \pmod {61}$ are $4,5,52. $

The first result is due to Gauss, the second to Jacobi. All necessary information is in the chapter on cubic and biquadratic reciprocity in Ireland and Rosen, but no information about algorithms for finding cube roots of general numbers mod general primes. So these were just illustrations. The Gauss result is Proposition 9.6.2 on page 119. The Jacobi result, in slightly different appearance, is Exercise 23 on page 135. I remain a little unclear what your cryptography class is expecting of you; there are algorithms for doing this, well publicized, but they were fairly difficult to invent in the first place. Certainly i have no idea what your background might be, especially what has been covered so far in your course.

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$.