二次剩余&&Cipolla

二次剩余

给定y和奇质数p，求x，使得\(x^2≡y(mod p)\)

勒让德符号(legendre symbol)

以前看视频的截图
求解\(x^2\equiv a(mod\ p)\)时，我们可用勒让德符号来判定他是否有解
（前提，p必须为奇素数）
\(\begin{pmatrix} \frac{a}{p} \end{pmatrix}=\begin{cases}0 (a\equiv 0(mod\ p))\\1(a\%p意义下是二次剩余)\\-1(a\%p意义下是二次非剩余)\end{cases}\)
有时为了印刷上的方便，会写成\((a|p)\)
0认为是特殊情况，这里不过分讨论

这里只说明第ii条，因为其他的都很显然(或者看完ii条之后)，iii说明只他是个完全积性函数

公式\((a|p)=a^{\frac{p-1}{2}}(mod\ p)\)

也许还可以叫欧拉判别法
首先证明\(a^{\frac{p-1}{2}}(mod\ p)=1或-1\)
\(a^{p-1}-1=(a^{\frac{p-1}{2}}+1)(a^{\frac{p-1}{2}}-1)\equiv 0 (mod\ p)\)
显然，\(a^{\frac{p-1}{2}}(mod\ p)只有=1或-1\)时，才可能成立

a为%p意义下的二次剩余时\(a^{\frac{p-1}{2}}\equiv 1(mod\ p)\)
\(x^{2}\equiv a(mod\ p)\)也可以说为\(x\equiv a^{\frac{1}{2}}\equiv x^{p-1}(mod\ p)\)
而费马小定理又可以得到\(x^{p-1}\equiv 1(mod\ p)\)
存在x

a为%p意义下的二次非剩余时\(a^{\frac{p-1}{2}}\equiv -1(mod\ p)\)
也就是\(x^{p-1}\equiv -1(mod\ p)\)
而费马小定理又可以得到\(x^{p-1}\equiv 1(mod\ p)\)
所以不存在x

结论1

1到\(p-1\)中有\(\frac{p-1}{2}\)个勒让德符号为1,\(\frac{p-1}{2}\)个勒让德符号为-1
在%p意义下，a,P−a平方的结果是一样的，1 到 P−1的平方就会有\(\frac{p-1}{2}\)个互不相同的数，剩下的就不是二次剩余

结论 2

\((a+b)^p≡a^p+b^p (Mod p)\)
证明:直接展开二项式定理，因为p是质数，除了i=0和p项，其他项分子的p分母都消不掉，会被模成0，剩下\(a^p+b^p\)

Cipolla's Algorithm.

求解\(x^2≡y(mod p)\)时
不断随机a，使得\(\begin{pmatrix} \frac{a^2-y}{p} \end{pmatrix}=-1\)
结论1可以知道，随机一两次就能找到
令\(w=\sqrt{a^2-y}，x=(a+w)^{\frac{p+1}{2}}\)

结论3 \(w^p\equiv -w\)

证明：\(w^p\equiv w^{p-1}*w\equiv (a^2-y)^{\frac{p-1}{2}}*w\equiv -w\)
\(x^2\equiv (a+w)^{p+1}\)
\(\ \ \ \ \equiv (a+w)^{p}(a+w)\)
结论2可知
\(\ \ \ \ \equiv (a^p+w^p)(a+w)\)
结论3又知
\(\ \ \ \ \equiv(a^{p-1}*a+w^{p-1}*w)(a+w)\)
\(\ \ \ \ \equiv(a-w)(a+w)\)
\(\ \ \ \ \equiv a^2-w^2\)
\(\ \ \ \ \equiv y\)
可w这个虚部咋计算，根据拉格朗日定理，虚部系数为0

代码

咕咕

end

太多摘抄qwq
主要参考https://blog.csdn.net/L_0_Forever_LF/article/details/79052135
wiki的图片很棒
附带一个题，不过没大有联系
求1000位数是否是完全平方数，yes or no
用几个模数多试几次，再勒让德符号判定一下是否有解