模平方根¶
来源：
密码学引论 / Mathematical-Foundations/模平方根.md
模为素数¶
\(p \equiv 3 \pmod 4\)的情况¶
注意到一个平凡的情况
\[
x^2 \equiv 1 \pmod p
\]
则\(x = 1,p-1\) 我们考虑费马小定理
\[
x^2 \equiv d \pmod p
\]
\[
x^{p-1} \equiv 1 \pmod p
\]
由于d是已知的，模素数是构成一个循环群的，我们可以在d的子群里找一下有没有平方根
\[
x = d^t \pmod p
\]
也就是说
\[
d^{2t-1} \equiv 1 \pmod p
\]
那么由欧拉准则
\[
d^\frac{p-1}{2} \equiv 1 \pmod p
\]
容易得到
\[
t = \frac{p+1}{4}
\]
所以就可以求解
\[
x = \pm d^{\frac{p+1}{4}} \pmod p
\]
\(p \equiv 1 \pmod 4\)的情况¶
Tonelli–Shanks algorithm¶
相关概念
Legendre符号
Jacobi符号
二次剩余