SqrtDem

Square Root Modulo P Algorithm

Calculate $\sqrt{a} \pmod{p}$ using Shanks' RESSOL algorithm

Base element $a$:

Prime modulus $p$:

Understanding Square Roots Modulo Prime

The square root modulo prime problem asks: given integers $a$ and prime $p$, find $x$ such that $x^2 \equiv a \pmod{p}$. Shanks' RESSOL algorithm efficiently solves this when a solution exists:

1. 1First, we check if $a$ is a quadratic residue modulo $p$ using Euler's criterion: $a^{(p-1)/2} \equiv 1 \pmod{p}$
2. 2For the special case where $p \equiv -1 \pmod{4}$, we can use the simple observation: $(a^{(p+1)/4})^2 \equiv a^{(p-1)/2} \times a \equiv a \pmod{p}$
3. 3For $p \equiv 1 \pmod{4}$, we factor $p-1 = 2^s \cdot m$ where $m$ is odd
4. 4We find a quadratic non-residue $z$ modulo $p$ (an element where $z^{(p-1)/2} \equiv -1 \pmod{p}$)
5. 5Using the Tonelli-Shanks algorithm, we iteratively reduce the problem until we find the square root
6. 6The algorithm maintains the invariant that we're solving $r^2 \equiv n \cdot a \pmod{p}$ where $n$ has decreasing order of 2