当你熟练掌握 Tonelli-Shanks 算法求解同余方程问题但是在处理多项式方程的根发现问题和以前有一点点不太一样在这里需要将模p pp的解提升到模p k p^kpk的解时别担心这时候 Hensel-lifting 算法 就像一把神奇的梯子能帮你一步步攀登到更高的解空间。欢迎来到《密码学核心算法实战》的 Hensel-lifting 专题这里没有纸上谈兵的理论空谈真的不画大饼只有一把把能直接撬动数据安全的精密齿轮⚙️。Hensel-lifting算法 Hensel-lifting 算法用于将模p pp的多项式方程的解提升到模p k p^kpk的解。具体来说如果我们有一个多项式f ( x ) f(x)f(x)和一个整数a aa满足f ( a ) ≡ 0 ( m o d p ) f(a) \equiv 0 \pmod{p}f(a)≡0(modp)并且f ′ ( a ) ≢ 0 ( m o d p ) f(a) \not\equiv 0 \pmod{p}f′(a)≡0(modp)那么 Hensel-lifting 算法可以帮助我们找到一个整数b bb使得f ( b ) ≡ 0 ( m o d p k ) f(b) \equiv 0 \pmod{p^k}f(b)≡0(modpk)。Hensel-lifting算法的原理 设k ≥ 1 k \geq 1k≥1是整数a aa在模p k p^kpk下的平方根是b bb即b 2 ≡ a ( m o d p k ) b^2 \equiv a \pmod{p^k}b2≡a(modpk)。目标利用b bb求出a aa在模p k 1 p^{k1}pk1下的平方根c cc。因为a 是模 p k 的二次剩余 ⟺ a 是模 p 的二次剩余 a \text{ 是模 } p^k \text{ 的二次剩余} \iff a \text{ 是模 } p \text{ 的二次剩余}a是模pk的二次剩余⟺a是模p的二次剩余所以c 2 ≡ a ( m o d p k 1 ) ⟹ c 2 ≡ a ( m o d p k ) ⟹ c 2 ≡ b 2 ( m o d p k ) ⟹ c ≡ ± b ( m o d p k ) \begin{align*} c^2 \equiv a \pmod{p^{k1}} \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*}c2≡a(modpk1)⟹c2≡a(modpk)⟹c2≡b2(modpk)⟹c≡±b(modpk)c ≡ ± b ( m o d p k ) c \equiv \pm b \pmod{p^k}c≡±b(modpk)所以设c ≡ b v p k c \equiv b vp^kc≡bvpk由于 $2t \geq t 1 $则有c 2 ≡ ( b v p k ) 2 ≡ b 2 2 b v p k v 2 p 2 k ≡ b 2 2 b v p k ( m o d p k 1 ) c^2 \equiv (b vp^k)^2 \equiv b^2 2bvp^k v^2p^{2k} \equiv b^2 2bvp^k \pmod{p^{k1}}c2≡(bvpk)2≡b22bvpkv2p2k≡b22bvpk(modpk1)已知c 2 ≡ a ( m o d p k 1 ) c^2 \equiv a \pmod{p^{k1}}c2≡a(modpk1)所以有a − b 2 ≡ 2 b v p k ( m o d p k 1 ) a - b^2 \equiv 2bvp^k \pmod{p^{k1}}a−b2≡2bvpk(modpk1)注意一个神奇的技巧p ∤ 2 b ⟹ gcd ( 2 b p k , p k 1 ) p k b 2 ≡ a ( m o d p k ) ⟹ p k ∣ ( a − b 2 ) \begin{align*} p \nmid 2b \implies \gcd(2bp^k, p^{k1}) p^k \\ b^2 \equiv a \pmod{p^k} \implies p^k | (a - b^2) \end{align*}p∤2b⟹gcd(2bpk,pk1)pkb2≡a(modpk)⟹pk∣(a−b2)所以我们直接对a − b 2 ≡ 2 b v p k ( m o d p k 1 ) a - b^2 \equiv 2bvp^k \pmod{p^{k1}}a−b2≡2bvpk(modpk1)使用消去律得到a − b 2 p k ≡ 2 b v ( m o d p ) v ≡ ( a − b 2 p k ) ( 2 b ) − 1 ( m o d p ) \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*}pka−b2v≡2bv(modp)≡(pka−b2)(2b)−1(modp)由此不断迭代就可以将模p pp的解提升到模p k p^kpk的解了。Hensel-lifting算法的实现 虽然 Hensel-lifting 算法的原理看起来有点抽象但它的操作步骤非常直接就是直接把v vv的计算公式套用到每次迭代中直到达到所需的k kk这里就直接演示了。下面是 Hensel-lifting 算法的一个简单实现fromsage.allimporttonelli_shanks,inverse_moddefhensel_lift(n,p,k):btonelli_shanks(n,p)t1while(t!k):v((n-b*b)//pow(p,t))%p c(bpow(p,t)*inverse_mod(2*b,p)*v)%pow(p,t1)bc t1returncSageMath 偷懒 有同学说“博主博主你的算法确实很厉害但是还是太吃操作了有没有更加简单无脑的用法”有的兄弟有的这样的算法在 SageMath 中早就已经被封装好了我们直接调用就行了fromsage.allimportsolve_mod,var# sage环境中才生效# 实际上solve_mod函数已经封装好了Hensel-lifting算法我们直接调用就行了xvar(x)mod7fx**3-8rsolve_mod(f,mod)实际上对于二次剩余问题SageMath 中的solve_mod函数已经内置了Tonelli-ShanksHensel-liftingCRT 算法所以一般情况下我们直接使用solve_mod就可以得到方程的解了不管模数是p pp或p k p^kpk或n nn。怎么样是不是非常简单我的个人blogAlice and Bobの神秘小屋 密码学算法 - Hensel-Lifting 算法
当你熟练掌握 Tonelli-Shanks 算法求解同余方程问题但是在处理多项式方程的根发现问题和以前有一点点不太一样在这里需要将模p pp的解提升到模p k p^kpk的解时别担心这时候 Hensel-lifting 算法 就像一把神奇的梯子能帮你一步步攀登到更高的解空间。欢迎来到《密码学核心算法实战》的 Hensel-lifting 专题这里没有纸上谈兵的理论空谈真的不画大饼只有一把把能直接撬动数据安全的精密齿轮⚙️。Hensel-lifting算法 Hensel-lifting 算法用于将模p pp的多项式方程的解提升到模p k p^kpk的解。具体来说如果我们有一个多项式f ( x ) f(x)f(x)和一个整数a aa满足f ( a ) ≡ 0 ( m o d p ) f(a) \equiv 0 \pmod{p}f(a)≡0(modp)并且f ′ ( a ) ≢ 0 ( m o d p ) f(a) \not\equiv 0 \pmod{p}f′(a)≡0(modp)那么 Hensel-lifting 算法可以帮助我们找到一个整数b bb使得f ( b ) ≡ 0 ( m o d p k ) f(b) \equiv 0 \pmod{p^k}f(b)≡0(modpk)。Hensel-lifting算法的原理 设k ≥ 1 k \geq 1k≥1是整数a aa在模p k p^kpk下的平方根是b bb即b 2 ≡ a ( m o d p k ) b^2 \equiv a \pmod{p^k}b2≡a(modpk)。目标利用b bb求出a aa在模p k 1 p^{k1}pk1下的平方根c cc。因为a 是模 p k 的二次剩余 ⟺ a 是模 p 的二次剩余 a \text{ 是模 } p^k \text{ 的二次剩余} \iff a \text{ 是模 } p \text{ 的二次剩余}a是模pk的二次剩余⟺a是模p的二次剩余所以c 2 ≡ a ( m o d p k 1 ) ⟹ c 2 ≡ a ( m o d p k ) ⟹ c 2 ≡ b 2 ( m o d p k ) ⟹ c ≡ ± b ( m o d p k ) \begin{align*} c^2 \equiv a \pmod{p^{k1}} \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*}c2≡a(modpk1)⟹c2≡a(modpk)⟹c2≡b2(modpk)⟹c≡±b(modpk)c ≡ ± b ( m o d p k ) c \equiv \pm b \pmod{p^k}c≡±b(modpk)所以设c ≡ b v p k c \equiv b vp^kc≡bvpk由于 $2t \geq t 1 $则有c 2 ≡ ( b v p k ) 2 ≡ b 2 2 b v p k v 2 p 2 k ≡ b 2 2 b v p k ( m o d p k 1 ) c^2 \equiv (b vp^k)^2 \equiv b^2 2bvp^k v^2p^{2k} \equiv b^2 2bvp^k \pmod{p^{k1}}c2≡(bvpk)2≡b22bvpkv2p2k≡b22bvpk(modpk1)已知c 2 ≡ a ( m o d p k 1 ) c^2 \equiv a \pmod{p^{k1}}c2≡a(modpk1)所以有a − b 2 ≡ 2 b v p k ( m o d p k 1 ) a - b^2 \equiv 2bvp^k \pmod{p^{k1}}a−b2≡2bvpk(modpk1)注意一个神奇的技巧p ∤ 2 b ⟹ gcd ( 2 b p k , p k 1 ) p k b 2 ≡ a ( m o d p k ) ⟹ p k ∣ ( a − b 2 ) \begin{align*} p \nmid 2b \implies \gcd(2bp^k, p^{k1}) p^k \\ b^2 \equiv a \pmod{p^k} \implies p^k | (a - b^2) \end{align*}p∤2b⟹gcd(2bpk,pk1)pkb2≡a(modpk)⟹pk∣(a−b2)所以我们直接对a − b 2 ≡ 2 b v p k ( m o d p k 1 ) a - b^2 \equiv 2bvp^k \pmod{p^{k1}}a−b2≡2bvpk(modpk1)使用消去律得到a − b 2 p k ≡ 2 b v ( m o d p ) v ≡ ( a − b 2 p k ) ( 2 b ) − 1 ( m o d p ) \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*}pka−b2v≡2bv(modp)≡(pka−b2)(2b)−1(modp)由此不断迭代就可以将模p pp的解提升到模p k p^kpk的解了。Hensel-lifting算法的实现 虽然 Hensel-lifting 算法的原理看起来有点抽象但它的操作步骤非常直接就是直接把v vv的计算公式套用到每次迭代中直到达到所需的k kk这里就直接演示了。下面是 Hensel-lifting 算法的一个简单实现fromsage.allimporttonelli_shanks,inverse_moddefhensel_lift(n,p,k):btonelli_shanks(n,p)t1while(t!k):v((n-b*b)//pow(p,t))%p c(bpow(p,t)*inverse_mod(2*b,p)*v)%pow(p,t1)bc t1returncSageMath 偷懒 有同学说“博主博主你的算法确实很厉害但是还是太吃操作了有没有更加简单无脑的用法”有的兄弟有的这样的算法在 SageMath 中早就已经被封装好了我们直接调用就行了fromsage.allimportsolve_mod,var# sage环境中才生效# 实际上solve_mod函数已经封装好了Hensel-lifting算法我们直接调用就行了xvar(x)mod7fx**3-8rsolve_mod(f,mod)实际上对于二次剩余问题SageMath 中的solve_mod函数已经内置了Tonelli-ShanksHensel-liftingCRT 算法所以一般情况下我们直接使用solve_mod就可以得到方程的解了不管模数是p pp或p k p^kpk或n nn。怎么样是不是非常简单我的个人blogAlice and Bobの神秘小屋