给定奇素数p和正整数x(1 定义:给定奇素数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^(e2)) * h^((t+1)2) ret rn b 托内利-尚克斯算法是概率算法,返回正确解的概率为12.算法的渐进时间复杂度为o((log p)^4).