密码学算法 - Tonelli-Shanks 算法

当你在椭圆曲线上进行加密操作时📐，需要计算某个点的平方根，但又发现这个点在有限域中没有平方根时😱，别担心，这时候 Tonelli-Shanks 算法 就像一把灵巧的钥匙🔑，能帮你在无解的荒漠中精准定位那唯一的坐标点。

欢迎来到《密码学核心算法实战》的 Tonelli-Shanks 专题！这里没有纸上谈兵的理论空谈（真的不画大饼😉），只有一把把能直接撬动数据安全的精密齿轮⚙️。

Tonelli-Shanks算法 🌟

Tonelli-Shanks 算法用于求解形如：

x

2

≡

a

(

m

o

d

p

)

x^2 \\equiv a \\pmod{p}

x2≡a(modp) 的同余方程，其中 $ p $ 是奇素数，$ a $ 是模 $ p $ 下的平方数。

Tonelli-Shanks算法的操作 🙃

输入：一个整数 $ a $ 和一个奇素数 $ p $，满足 $ a $ 是模 $ p $ 下的平方数。则 $ (\\frac{a}{p}) = 1 $。 输出：一个整数 $ x $，满足 $ x^2 \\equiv a \\pmod{p} $。

算法步骤：

Tonelli-Shanks算法的原理 😭

已知

p

−

1

=

Q

⋅

2

s

r

≡

a

Q

+

1

2

(

m

o

d

p

)

t

≡

a

Q

(

m

o

d

p

)

\\begin{align*} p – 1 = Q \\cdot 2^s \\\\ r \\equiv a^{\\frac{Q+1}{2}} \\pmod{p} \\\\ t \\equiv a^Q \\pmod{p} \\end{align*}

p−1=Q⋅2sr≡a2Q+1​(modp)t≡aQ(modp)​

所以，

r

2

≡

a

t

(

m

o

d

p

)

r^2 \\equiv at \\pmod{p}

r2≡at(modp)，对于每次迭代都为真。

如果

t

≡

1

(

m

o

d

p

)

t \\equiv 1 \\pmod{p}

t≡1(modp)，则

r

2

≡

a

(

m

o

d

p

)

r^2 \\equiv a \\pmod{p}

r2≡a(modp)，并且

x

≡

±

r

(

m

o

d

p

)

x \\equiv \\pm r \\pmod{p}

x≡±r(modp)，算法结束。

如果

t

≢

1

(

m

o

d

p

)

t \\not\\equiv 1 \\pmod{p}

t≡1(modp)，那么认为

z

z

z 为模

p

p

p 的平方非剩余。 令

c

≡

z

Q

(

m

o

d

p

)

c \\equiv z^Q \\pmod{p}

c≡zQ(modp)，那么

c

2

s

≡

z

Q

⋅

2

s

≡

z

p

−

1

≡

1

(

m

o

d

p

)

c^{2^s} \\equiv z^{Q \\cdot 2^s} \\equiv z^{p-1} \\equiv 1 \\pmod{p}

c2s≡zQ⋅2s≡zp−1≡1(modp)

并且

c

2

s

−

1

≡

z

Q

⋅

2

s

−

1

≡

z

p

−

1

2

≡

−

1

(

m

o

d

p

)

c^{2^{s-1}} \\equiv z^{Q \\cdot 2^{s-1}} \\equiv z^{\\frac{p-1}{2}} \\equiv -1 \\pmod{p}

c2s−1≡zQ⋅2s−1≡z2p−1​≡−1(modp)

所以

c

c

c 的乘法阶为

2

s

2^s

2s。

同理，有

t

2

s

≡

1

(

m

o

d

p

)

t^{2^s} \\equiv 1 \\pmod{p}

t2s≡1(modp)，所以

t

t

t 的乘法阶整除

2

s

2^s

2s。 假设

t

t

t 的乘法阶为

2

s

∗

2^{s^*}

2s∗，由于

a

a

a 是模

p

p

p 的平方剩余，所以

t

≡

a

Q

≡

1

(

m

o

d

p

)

t \\equiv a^Q \\equiv 1 \\pmod{p}

t≡aQ≡1(modp)也是一个平方，所以

s

∗

<

s

−

1

s^* < s – 1

s∗<s−1。

之后令

b

≡

c

2

s

−

s

∗

−

1

(

m

o

d

p

)

r

∗

≡

r

⋅

b

(

m

o

d

p

)

c

∗

≡

b

2

(

m

o

d

p

)

t

∗

≡

t

⋅

c

∗

(

m

o

d

p

)

\\begin{align*}b \\equiv c^{2^{s – s^* – 1}} \\pmod{p} \\\\ r^* \\equiv r \\cdot b \\pmod{p} \\\\ c^* \\equiv b^2 \\pmod{p} \\\\ t^* \\equiv t \\cdot c^* \\pmod{p} \\end{align*}

b≡c2s−s∗−1(modp)r∗≡r⋅b(modp)c∗≡b2(modp)t∗≡t⋅c∗(modp)​

和上述一致，有

(

r

∗

)

2

≡

a

t

∗

(

m

o

d

p

)

(r^*)^2 \\equiv a t^* \\pmod{p}

(r∗)2≡at∗(modp) 成立。

然而

t

t

t 和

c

∗

c^*

c∗ 的阶都是

2

s

∗

2^{s^*}

2s∗，所以

t

∗

t^*

t∗ 的阶数为

2

s

∗

∗

2^{s^**}

2s∗∗ 满足

s

∗

∗

<

s

∗

s^** < s^*

s∗∗<s∗。

如果

s

∗

∗

=

0

s^** = 0

s∗∗=0，则

t

∗

≡

1

(

m

o

d

p

)

t^* \\equiv 1 \\pmod{p}

t∗≡1(modp)，并且

x

≡

±

r

∗

(

m

o

d

p

)

x \\equiv \\pm r^* \\pmod{p}

x≡±r∗(modp)，算法结束。 否则，用

r

∗

r^*

r∗、

t

∗

t^*

t∗ 和

c

∗

c^*

c∗ 替换

r

r

r、

t

t

t 和

c

c

c，继续迭代重新开始循环，直到

s

∗

…

∗

s^{* \\ldots *}

s∗…∗。 因此，一系列的

s

s

s 是属于严格减少的算法，一定会终止。

Tonelli-Shanks算法的实现 🤠

看懂了吗，下面是 Tonelli-Shanks 算法的一个简单实现：

def tonelli_shanks(n, p):
if n == 0:
return 0
if pow(n, (p – 1) // 2, p) != 1: # 如果 n 不是模 p 的平方剩余，则没有解
print("No square root exists")
return None
if p % 4 == 3: # 如果 p ≡ 3 (mod 4)，直接计算平方根
return pow(n, (p + 1) // 4, p)

q = p – 1 # 将 p-1 分解为 Q * 2^s
s = 0
while q % 2 == 0:
s += 1
q //= 2
# 找到一个非平方数 z
z = 2
while pow(z, (p – 1) // 2, p) != p – 1:
z += 1
c = pow(z, q, p)
x = pow(n, (q + 1) // 2, p)
t = pow(n, q, p)
m = s
# 开始迭代
while t != 1:
i = 1
t2 = pow(t, 2, p)
while t2 != 1:
t2 = pow(t2, 2, p)
i += 1
b = pow(c, 1 << (m – i – 1), p) # c^(2^(m-i-1))
x = (x * b) % p
t = (t * b * b) % p
c = (b * b) % p
m = i
return x, p – x

SageMath 偷懒 🤓👆

有同学说：“博主，博主，你的算法确实很厉害，但是还是太吃操作了，有没有更加简单无脑的用法？”👻 有的，兄弟有的，这样的算法在 SageMath 中早就已经被封装好了🤫，我们直接调用就行了：

from sage.all import solve_mod, var # sage环境中才生效
# solve_mod 中已经有 Tonelli-Shanks 算法的实现了，直接用就好
x = var('x') # 一定要记得定义变量，不然会报错的哦
mod = 7
f = x**2 – 4
r = solve_mod(f, mod)

怎么样，是不是非常简单？🤣👉🤡

我的个人blog：Alice and Bobの神秘小屋