密码学算法 - Hensel-Lifting 算法 | Alice and Bobの神秘小屋

当你熟练掌握 Tonelli-Shanks 算法求解同余方程问题，但是在处理多项式方程的根📐，发现问题和以前有一点点不太一样，在这里需要将模 $p$ 的解提升到模 $p^k$ 的解时😱，别担心，这时候 Hensel-lifting 算法就像一把神奇的梯子🪜，能帮你一步步攀登到更高的解空间。

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

Hensel-lifting算法 🌟

Hensel-lifting 算法用于将模 $p$ 的多项式方程的解提升到模 $p^k$ 的解。具体来说，如果我们有一个多项式 $f(x)$ 和一个整数 $a$，满足 $f(a) \equiv 0 \pmod{p}$，并且 $f’(a) \not\equiv 0 \pmod{p}$，那么 Hensel-lifting 算法可以帮助我们找到一个整数 $b$，使得 $f(b) \equiv 0 \pmod{p^k}$。

Hensel-lifting算法的原理 😵

设 $k \geq 1$ 是整数，$a$ 在模 $p^k$ 下的平方根是 $b$，即 $b^2 \equiv a \pmod{p^k}$。
目标：利用 $b$，求出 $a$ 在模 $p^{k+1}$ 下的平方根 $c$。

因为$a \text{ 是模 } p^k \text{ 的二次剩余} \iff a \text{ 是模 } p \text{ 的二次剩余}$
所以

$\begin{align*} c^2 \equiv a \pmod{p^{k+1}} &\implies c^2 \equiv a \pmod{p^k} \\ &\implies c^2 \equiv b^2 \pmod{p^k} \\ &\implies c \equiv \pm b \pmod{p^k} \end{align*}$

$c \equiv \pm b \pmod{p^k}$，所以设 $c \equiv b + vp^k$，由于 $2t \geq t +1 $，则有

$c^2 \equiv (b + vp^k)^2 \equiv b^2 + 2bvp^k + v^2p^{2k} \equiv b^2 + 2bvp^k \pmod{p^{k+1}}$

已知 $c^2 \equiv a \pmod{p^{k+1}}$，所以有

$a - b^2 \equiv 2bvp^k \pmod{p^{k+1}}$

注意，一个神奇的技巧：

$\begin{align*} p \nmid 2b \implies \gcd(2bp^k, p^{k+1}) = p^k \\ b^2 \equiv a \pmod{p^k} \implies p^k | (a - b^2) \end{align*}$

所以我们直接对 $a - b^2 \equiv 2bvp^k \pmod{p^{k+1}}$ 使用消去律得到：

$\begin{align*} \frac{a - b^2}{p^k} &\equiv 2bv \pmod{p} \\ v &\equiv (\frac{a - b^2}{p^k})(2b)^{-1} \pmod{p} \end{align*}$

由此不断迭代，就可以将模 $p$ 的解提升到模 $p^k$ 的解了。

Hensel-lifting算法的实现 🙃

虽然 Hensel-lifting 算法的原理看起来有点抽象，但它的操作步骤非常直接，就是直接把 $v$ 的计算公式套用到每次迭代中，直到达到所需的 $k$，这里就直接演示了。

下面是 Hensel-lifting 算法的一个简单实现：

from sage.all import tonelli_shanks, inverse_mod

def hensel_lift(n, p, k):
    b = tonelli_shanks(n, p)
    t = 1
    while (t != k):
        v = ((n - b*b)//pow(p,t)) % p
        c = (b + pow(p,t)*inverse_mod(2*b, p)*v) % pow(p,t+1)
        b = c
        t += 1
    return c

SageMath 偷懒 🤓👆

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

from sage.all import solve_mod, var # sage环境中才生效
# 实际上solve_mod函数已经封装好了Hensel-lifting算法，我们直接调用就行了
x = var('x')
mod = 7
f = x**3 - 8
r = solve_mod(f, mod)

实际上，对于二次剩余问题，SageMath 中的 solve_mod 函数已经内置了Tonelli-Shanks，Hensel-lifting，CRT 算法，所以一般情况下，我们直接使用 solve_mod 就可以得到方程的解了（不管模数是 $p$ 或 $p^k$ 或 $n$）。

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

上一章：密码学算法 - Tonelli-Shanks算法 👈
下一章：密码学算法 - 连分数算法 👈
回到开始：关于我 👈

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