升幂引理（Hensel's Lemma）详解：定义、应用及代码实现

升幂引理（Hensel's Lemma）详解：定义、应用及代码实现

引用

CSDN

1.

https://m.blog.csdn.net/tang7mj/article/details/139014836

升幂引理（Hensel's Lemma）是数论中的一个重要工具，尤其在模数为质数幂的情况下，用于求解多项式方程和同余方程的高次幂解。它广泛应用于算法竞赛（如ACM-ICPC）、计算机科学以及数论中的许多问题。本文将详细介绍升幂引理的定义、应用以及代码实现。

升幂引理的定义

升幂引理提供了一种从模 𝑝p 的解提升到模 𝑝𝑘pk 的解的方法。具体来说，假设 𝑓(𝑥)f(x) 是一个多项式，𝑝p 是一个质数，且我们已知 𝑓(𝑥)≡0(mod𝑝)f(x)≡0(modp) 的某个解 𝑥0x0 ，升幂引理可以用于找到模 𝑝𝑘pk 的解。

升幂引理的基本形式

设 𝑝p 为一个质数，𝑘k 为正整数。如果 𝑥0x0 是方程 𝑓(𝑥)≡0(mod𝑝𝑘)f(x)≡0(modpk) 的解，且 𝑓′(𝑥0)≢0(mod𝑝)f′(x0 )≡0(modp)，那么存在唯一的 𝑥1x1 满足：

𝑥1≡𝑥0(mod𝑝𝑘)x1 ≡x0 (modpk) 𝑓(𝑥1)≡0(mod𝑝𝑘+1)f(x1 )≡0(modpk+1)

升幂引理的应用

升幂引理主要用于解决以下问题：

1. 求解高次同余方程：通过已知模 𝑝p 的解，逐步提升到模 𝑝𝑘pk 的解。
2. 数论中的多项式方程：在模数为质数幂的情况下，求解多项式方程。

具体求解步骤

1. 初始解的确定：找到 𝑓(𝑥)≡0(mod𝑝)f(x)≡0(modp) 的解 𝑥0x0 。
2. 计算导数：计算 𝑓′(𝑥0)f′(x0 ) 并确认 𝑓′(𝑥0)≢0(mod𝑝)f′(x0 )≡0(modp)。
3. 升幂过程：

• 计算 𝑓(𝑥0)f(x0 ) 和 𝑓′(𝑥0)f′(x0 ) 的模 𝑝𝑘pk 值。
• 根据公式计算新的解 𝑥1x1 ，使得 𝑥1≡𝑥0(mod𝑝𝑘)x1 ≡x0 (modpk)。

实现代码

C++ 实现

#include <iostream>
using namespace std;
// 扩展欧几里得算法求逆元
int ex_gcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = ex_gcd(b, a % b, x, y);
    int temp = x;
    x = y;
    y = temp - a / b * y;
    return d;
}
// 模逆元求解
int mod_inverse(int a, int p) {
    int x, y;
    int g = ex_gcd(a, p, x, y);
    if (g != 1) {
        throw "No modular inverse!";
    }
    return (x % p + p) % p;
}
// 升幂引理
int hensel_lifting(int f(int), int fp(int), int x0, int p, int k) {
    int x = x0;
    for (int i = 1; i <= k; ++i) {
        int r = f(x) / (p * i);
        int fp_inv = mod_inverse(fp(x), p);
        x = (x - r * fp_inv % p * p) % (p * i);
    }
    return x;
}
// 示例函数
int f(int x) {
    return x * x - 2;
}
int fp(int x) {
    return 2 * x;
}
int main() {
    int p = 5;  // 质数
    int k = 2;  // 升幂次数
    int x0 = 3; // 模 p 的解
    try {
        int result = hensel_lifting(f, fp, x0, p, k);
        cout << "The solution is: " << result << endl;
    } catch (const char* msg) {
        cerr << msg << endl;
    }
    return 0;
}

实例讲解

例题

假设我们要求解方程 𝑥2−2≡0(mod25)x2−2≡0(mod25)，已知 𝑥0=3x0 =3 是方程在模 5 下的解。

解法

1. 确定初始解 𝑥0=3x0 =3。
2. 计算导数 𝑓′(𝑥)=2𝑥f′(x)=2x，确认 𝑓′(𝑥0)=6≢0(mod5)f′(x0 )=6≡0(mod5)。
3. 使用升幂引理提升解：

• 初始解为 𝑥0=3x0 =3。
• 计算 𝑥1x1 使得 𝑥1≡3(mod5)x1 ≡3(mod5) 且 𝑥12−2≡0(mod25)x12 −2≡0(mod25)。
• 经过升幂过程得到最终解 𝑥1=8x1 =8。

应用

升幂引理在许多实际问题中都有应用，例如：

1. 数论研究：用于求解模数为质数幂的多项式方程。
2. 算法竞赛：解决复杂的同余方程问题。
3. 计算机科学：密码学中的高次同余方程求解。

总结

本节介绍了升幂引理的基本定义、应用步骤、实例讲解以及代码实现。掌握这些内容，对于理解数论中的许多问题和算法竞赛中的高效解题具有重要意义。通过代码示例，读者可以更好地理解和应用升幂引理解决实际问题。