密码学算法 - Tonelli-Shanks 算法 | Alice and Bobの神秘小屋

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

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

Tonelli-Shanks算法 🌟

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

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

的同余方程，其中 $ p $ 是奇素数，$ a $ 是模 $ p $ 下的平方数。

Tonelli-Shanks算法的操作 🙃

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

算法步骤：

将 $ p-1 $ 分解为 $ Q \cdot 2^s $，其中 $ Q $ 是奇数。
（如果 $s = 1$，即 $ p \equiv 3 \pmod{4} $，则直接计算 $ x \equiv \pm a^{\frac{p+1}{4}} \pmod{p} $）
找到一个非平方数 $ z $，即满足 $ (\frac{z}{p}) = -1 $ 的整数，令 $ c \equiv z^Q \pmod{p} $。
令 $ x \equiv a^{\frac{Q+1}{2}} \pmod{p} $，$ t \equiv a^Q \pmod{p} $，$ m = s $。
循环：
- 如果 $ t \equiv 1 \pmod{p} $，则返回 $ x $。
- 否则，找一个最小的 $ i $，使得 $ t^{2^i} \equiv 1 \pmod{p} $（重复平方）。
- 令 $ b \equiv c^{2^{m-i-1}} \pmod{p} $，更新 $ x \equiv x \cdot b \pmod{p} $，$ t \equiv t \cdot b^2 \pmod{p} $，$ c \equiv b^2 \pmod{p} $，$ m = i $。
- 如果 $x$ 是一个解，那么第二个解为 $p - x$。

Tonelli-Shanks算法的原理 😭

已知

$\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*}$

所以，$r^2 \equiv at \pmod{p}$，对于每次迭代都为真。

如果 $t \equiv 1 \pmod{p}$，则 $r^2 \equiv a \pmod{p}$，并且 $x \equiv \pm r \pmod{p}$，算法结束。

如果 $t \not\equiv 1 \pmod{p}$，那么认为 $z$ 为模 $p$ 的平方非剩余。
令 $c \equiv z^Q \pmod{p}$，那么

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

并且

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

所以 $c$ 的乘法阶为 $2^s$。

同理，有 $t^{2^s} \equiv 1 \pmod{p}$，所以 $t$ 的乘法阶整除 $2^s$。
假设 $t$ 的乘法阶为 $2^{s^}$，由于 $a$ 是模 $p$ 的平方剩余，所以 $t \equiv a^Q \equiv 1 \pmod{p}$也是一个平方，所以 $s^ < s - 1$。

之后令

$\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*}$

和上述一致，有 $(r^)^2 \equiv a t^ \pmod{p}$ 成立。

然而 $t$ 和 $c^$ 的阶都是 $2^{s^}$，所以 $t^$ 的阶数为 $2^{s^}$ 满足 $s^ < s^$。

如果 $s^* = 0$，则 $t^ \equiv 1 \pmod{p}$，并且 $x \equiv \pm r^ \pmod{p}$，算法结束。
否则，用 $r^$、$t^$ 和 $c^$ 替换 $r$、$t$ 和 $c$，继续迭代重新开始循环，直到 $s^{ \ldots }$。
因此，一系列的 $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)

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

上一章：密码学算法 - 中国剩余定理CRT 👈
下一章：密码学算法 - Hensel-lifting算法 👈
回到开始：关于我 👈

相关链接：
密码学数学基础 - 二次剩余 👈