二次剩余学习笔记
注意，下面的运算都是在模意义下进行的。
给定 \(n\)，求 \(x^2\equiv n\)
\(x\) 存在条件为 \(n^{\frac {p-1}2}=1\)，证明用费马小定理，略。
如何求出 \(x\)，随机一个 不存在 二次剩余的值 \(a^2-n\)，设为 \(w^2\)
这里可以把 \(w\) 理解为一个虚数。由于 \(w^2\) 不存在二次剩余，所以
\[w^p=w^{p-1}\times w=(w^2)^{\frac {p-1}2}\times w=(a^2-
n)^{\frac{p-1}2}\times w=(-1)\times w=-w\]
那么 \((a+w)^{p+1}=(a_p+w_p)(a+w)=(a-w)(a+w)=a^2-w^2=n\)
我们要求 \((a+w)^{\frac{p+1}2}\)，可以扩域计算。