Find the least positive integer $x$ such that $x^2 \equiv 30 \pmod{101}$ 
Find the least positive integer $x$ such that $x^2 \equiv 30 \pmod{101}$

This is the first time I have encountered this kind of problem, I have searched on the Internet but got no results. Is there a formula or an algorithm to solve this kind of problem? I would be very appreciative of your support!
 A: The "brute force" approach would be to try each $x$ from $1$ up to $101$. We can be sure that we won't have to try larger $x$, because if $x \equiv y \pmod{101}$, then $x^2 \equiv y^2 \pmod{101}$.
Here's a less tedious approach that relies on the facts that $101$ is prime and $101 \equiv 5 \pmod{8}$. A proof of the following claim can be found in section 1.5 of this textbook.
Claim: Suppose $p$ is a prime with $p \equiv 5 \pmod{8}$, and suppose $x^2 \equiv a \pmod{p}$. Then $x \equiv \pm a^{(p + 3)/8} \pmod{p}$ or $x \equiv \pm 2a \cdot (4a)^{(p - 5)/8} \pmod{p}$.
In our case, $p = 101$ and $a = 30$. You can quickly compute the values $a^{(p + 3)/8}$ and $2a \cdot (4a)^{(p - 5)/8}$ modulo $101$ using repeated squaring.
If we were working modulo some other prime $p$, the Tonelli-Shanks algorithm would be a good approach. What if we were working modulo a large composite number $n$? It is conjectured that there does not exist an efficient algorithm for solving a given equation of the form $x^2 \equiv a \pmod{n}$. An efficient algorithm for that problem could be used to factor large integers and thereby break important cryptosystems such as RSA.
