If we are working with a residue number system and start with $k$ such that $0 \le k < p$, how quickly can we find $n$ such that $0 \le n < p$ and $n \equiv k^2 \bmod p$? We know, additionally, that $p$ is prime.
I'd prefer to use as little "memory" or space as possible, but I won't reject something that seems to use it efficiently. Sorry I can't be more precise than this, but I'm just trying to get a good algorithm.
SOME IDEAS
We know that $k^2$ is equal to the sum of the first $k$ odd naturals.
There are (at most) two such numbers that, when squared, equal $n$ for some $k$, as shown in this question.