模平方根

定义给定奇素数p和正整数x（1<=x<=p-1）, 如果存在一个整数y，1<=y<=p-1, 使得x ≡ y*y (mod p) ，则称y是x的模p平方根。

举例63是55的模103平方根，因为有：63 * 63 ≡ 3969 ≡ 55 (mod 103)。

计算模平方根托内利－尚克斯算法可以计算模平方根。算法的流程如下：

输入奇素数p和正整数x（1<=x<=p-1）

随机选取g

设 p-1 = 2g * t，t为奇数

e=0

for(i=2;i<=s;i++)if((x*g^-e)^((p-1)/2^i) != 1)e += 2^i

h = x * g^-e

b = (g^(e/2)) * h^((t+1)/2)

return b

托内利－尚克斯算法是概率算法，返回正确解的概率为1/2。算法的渐进时间复杂度为O((log p)^4)。