Preface

今天z大神给我们讲数论和代数，然后后面讲了几个超级神的算法。Cipolla算是其中一个吧。貌似国内直接查名字还没有什么资料，查二次剩余的算法有ACdreamer简略的介绍。今天听讲时算是听懂了大半，回来又搞鼓了整个晚上才算完全弄明白。这个算法真的是从头到尾都是脑洞，太神了！
详细的解释见维基百科。

---

Paper

首先我们要弄清楚什么叫二次剩余，其实就是对于给定的p(p∈P)和n，如果有x满足x2≡n(modp)，那么n在模p意义下就是二次剩余。说白了就是模意义下能否开根号。
我们只讨论p为奇素数的情况。
我们先定义Fp，这是一个数域，其实就是0到p−1这p个数与模p意义下加减乘除运算构成的集合。

• 定理1：对于x2≡n(modp)，总共有p−12个的n能使该方程有解（将n=0情况除去，由于该情况显然有x=0）。
• 证明：我们只用考虑所有x2。如果存在不同的两个数u、v，它们的平方在模p意义下同余，那么显然有p|(u2−v2)。由平方差公式p|(u+v)(u−v)。显然p不可能整除u−v，因此p整除u+v，因此u+v≡0(modp)。这个结论反过来也是成立的，因此共有p−12种互不相同的平方，显然对应了所有有解的n，而且同一个n还一定存在两个互为相反数的解。

然后我们还要知道一个神奇的东西叫做勒让德符号(Legendre symbol)。
它是这样定义的
(ap)=⎧⎩⎨1,−1,0,a在模p意义下是二次剩余a在模p意义下是非二次剩余a≡0(modp)
那我们怎么求该符号的值呢？

• 定理2：(ap)≡ap−12(modp)
• 证明：
  
  • 当a在模p意义下是二次剩余时，令x2≡a(modp)，那么就有