模平方根

給定奇素數p和正整數x（1<=x<=p-1）, 如果存在一個整數y，1<=y<=p-1, 使得x ≡ y*y (mod p) ，則稱y是x的模p平方根。

基本介紹

• 中文名：模平方根
• 定義： 使得x ≡ y*y
• 計算：托內利－尚克斯算法
• 舉例：63是55的模103平方根

舉例

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)。