指导思想

https://en.wikipedia.org/wiki/Cipolla%27s_algorithm http://www.sciencedirect.com/science/article/pii/S0893965902000319

寻找模平方剩余

问题模型

给出质数p和整数a，求所有满足x2≡a(modp)的x。

Cipolla’s Algorithm

a=0或p=2的情况特殊判断。 定义二次剩余符号(ap)≡ap−12(modp)，当其为1时表示a是二次剩余。 找到一个w使得w2−a不是二次剩余，随机测试的期望次数为2。 在扩域上计算(w+w2−a−−−−−−√)p+12，则为一个可行的x，另外一个可行解为−x。 利用复数域的知识即可证明生成算法的正确性，时间复杂度O(logp)。

寻找模立方剩余

问题模型

给出质数p和整数a，求所有满足x3≡a(modp)的x。

Peralta Method Extension

a=0或p≤3的情况特殊判断。 如果p≡−1(mod3)，则x≡a2p−13(modp)是唯一解。 否则(−3p)=1，则ϵ=−3√−12为三次单位根，即ϵ3≡1(modp)。 此时有三分之一的数字是三次剩余，定义三次剩余符号[ap]≡ap−13(modp)，当其为1时表示a是二次剩余。 如果找到一个x，则其他解为xϵ,xϵ2。 类似二次剩余的证明方法，对于a的立方根x，构造群R={∑2i=0fixi|fi∈Zp,i=0,1,2}，可以证明R与Zp×Zp×