I was trying to solve the following equation:
$$y = x^2 \bmod p$$
where $p$ is prime.
I was trying to find an algorithm that solved this and that was in BPP (I don't think there is one in P). I know it exists so an explanation of the algorithm or a link to somewhere it is explained would be great!
If someone knows the name of these algorithms it would be great! (its easier to google them or look for them)
The standard algorithms (Cipolla or Tonelli-Shanks) are in BPP. The only probabilistic part in those algorithms is to find a quadratic non-residue mod $p$, this succeeds with probability only $\frac{p-1}{2p}$, but the probability can be made arbitrarily low by just making enough random picks, which doesn't hurt the polynomial running time. The Wikipedia articles on those algorithms are not very good; I especially like the book of Crandall and Pomerance for such topics.
Wikipedia links: en.wikipedia.org/wiki/Cipolla%27s_algorithm en.wikipedia.org/wiki/Tonelli-Shanks_algorithm