模平方根算法

模平方根算法求 $x^2\equiv a\pmod p$ 的解，是二次剩余理论的算法化：先用欧拉准则判可解，再用 Tonelli–Shanks 算法求根。它是有限域算术与椭圆曲线密码（点压缩恢复坐标）中的常用原语。

可解性判断

对奇素数 $p$、$p\nmid a$，$a$ 是二次剩余当且仅当 $a^{(p-1)/2}\equiv1\pmod p$（欧拉准则）。

简单情形

$p\equiv3\pmod4$（即 $p-1$ 中 $2$ 的幂次 $s=1$）时：$x\equiv a^{(p+1)/4}\pmod p$。

Tonelli–Shanks 算法

写 $p-1=q\cdot2^s$（$q$ 为奇数）。取一个非二次剩余 $z$，令 $c=z^q$，$x=a^{(q+1)/2}$，$t=a^q$，$m=s$。循环：

1. 若 $t\equiv1$，结束，$x$ 即平方根
2. 否则找最小 $i$（$1\le i<m$）使 $t^{2^i}\equiv1$，令 $b=c^{2^{m-i-1}}$
3. 更新 $x\leftarrow xb$，$t\leftarrow tb^2$，$c\leftarrow b^2$，$m\leftarrow i$，回到第 1 步

示例

求 $x^2\equiv2\pmod{17}$：$p-1=16=1\cdot2^4$，$q=1$，$s=4$。$3$ 是非二次剩余（$3^8\equiv-1$），故 $c=3$，$x=2$，$t=2$，$m=4$。

• $t=2\ne1$：$t^2=4$，$t^4\equiv-1$，$t^8\equiv1$ → $i=3$；$b=3^{2^0}=3$，$x\equiv6$，$t=2\cdot3^2\equiv1$，$m=3$
• $t\equiv1$，结束：$x=6$，且 $6^2=36\equiv2\pmod{17}$ ✓

应用

在有限域 $\mathbb{F}_p$ 上开方是椭圆曲线密码（如由横坐标恢复纵坐标）与若干后量子方案的子程序；$p\equiv3\pmod4$ 的特例在密码实现中大量使用。