On the Inversion Modulo a Power of an Integer

本文提出了两种通用算法：一种基于小学乘法思想，适用于计算任意互质整数 $a$ 对 $n^k$ 的模逆，并能利用计算机架构特性（如 $n=2^{64}$）显著提升效率；另一种则是对 Dumas 和 Hurchalla 针对 $p^{2^s}$ 模数的 Hensel 提升方法的推广，使其适用于任意整数 $n>1$ 的 $n^{2^s}$ 模数情形。

要点

这篇论文主要解决了一个在计算机数学中非常基础但又很棘手的问题：如何快速找到一个数的“倒数”（逆元），而且是在一个特殊的“模”运算环境下。

为了让你轻松理解，我们可以把这篇论文的内容想象成**“在特殊的数字世界里，如何快速找到一把万能钥匙”**。

1. 背景：什么是“模运算”和“逆元”？

想象你有一个巨大的时钟，但这个时钟不是 12 小时制的，而是 $n^k$ 小时制的（比如 $10^6$小时，或者$2^{64}$ 小时）。

• 模运算（Modulo）：就是在这个时钟上转圈。比如 $13 \pmod{12}$ 就是 1，因为转了一圈多 1 小时。
• 逆元（Inverse）：在普通数学里，2 的倒数是 0.5（因为 $2 \times 0.5 = 1$）。但在时钟世界里，没有小数。我们找的是另一个整数$x$，使得$a \times x$ 在时钟上刚好转回起点（也就是余数为 1）。
  • 比如：在 12 小时时钟上，5 的逆元是 5，因为 $5 \times 5 = 25$，25 除以 12 余 1。

为什么要找这个？
在现代密码学（如 RSA 加密、区块链）中，计算机需要疯狂地做这种“找逆元”的操作。如果找得慢，整个系统就会卡死。所以，越快越好。

2. 以前的方法：要么太死板，要么太复杂

在论文发表之前，科学家们主要有两种找钥匙的方法：

• 方法 A（Koç 算法）：

  • 适用场景：只能处理时钟是质数（如 2, 3, 5, 7...）的幂次方（比如 $2^{64}$或$5^{100}$）。
  • 特点：像是一个精密的瑞士军刀，步骤很简洁，每一步只做“加法”和“右移”（相当于除以 2）。
  • 缺点：如果时钟的基数不是质数（比如是 10，或者 12），这个方法就失效了。

• 方法 B（Hensel 提升法/Dumas & Hurchalla）：

  • 适用场景：也是针对质数幂，特别是 $2^s$（计算机最擅长的二进制）。
  • 特点：像是一个“倍增器”。先算出一个小范围的钥匙，然后像滚雪球一样，每次把范围扩大一倍（$2 \to 4 \to 8 \to 16$），直到覆盖整个时钟。
  • 缺点：虽然快，但依然被限制在“质数幂”这个框架里。

3. 这篇论文的两大贡献：更通用的“万能钥匙”

作者 Guangwu Xu 和他的团队提出了两个新想法，让找钥匙变得更通用、更灵活。

贡献一：像“小学数学乘法”一样找逆元（通用版）

• 核心思想：作者发现，找逆元的过程，其实和我们小时候学的竖式乘法（Schoolbook Multiplication）是一模一样的，只是方向反过来了。
• 比喻：
  • 想象你在做乘法竖式，从右往左一位一位地算。
  • 以前的算法像是在解复杂的方程组，需要很多步骤。
  • 新算法则是直接利用计算机的**“进位”机制**。就像你算 $99 \times 99$ 时，个位满 10 进 1 一样，新算法利用这个“进位”来一步步修正答案。
• 厉害在哪里？
  • 不再挑剔基数：以前的算法要求时钟必须是质数（如 2, 5）。新算法说：“不管你的时钟是 10 进制、12 进制，还是 64 位计算机原生的 $2^{64}$，我都能算！”
  • 利用硬件优势：现代电脑最擅长处理 64 位（$2^{64}$）甚至 128 位的数字。新算法直接利用电脑内部的“大数字加法器”，就像用大卡车运货，比用小推车（以前的算法）快得多。
  • 实验结果：在测试中，新算法比以前的方法快了几十倍甚至上百倍。

贡献二：把“倍增法”推广到任何数字（升级版）

• 核心思想：作者把 Dumas 和 Hurchalla 的“倍增法”（先算小的，再翻倍）进行了数学上的推广。
• 比喻：
  • 以前的倍增法只能处理“二进制”的倍增（$2 \to 4 \to 8$）。
  • 新算法说：我们可以把这个逻辑套用到任何数字 $n$ 上。比如，我们可以从 $n$ 开始，跳到 $n^2$，再跳到 $n^4$，直到覆盖整个范围。
• 意义：这打破了“必须是质数”的限制，让这种高效的倍增策略也能用在非质数的模运算上。

4. 总结：这对我们意味着什么？

你可以把这篇论文想象成给计算机算数系统升级了“变速箱”：

1. 以前：如果你要算一个复杂数字的逆元，计算机可能得用“手动挡”，一步步慢慢推，而且只支持特定的车型（质数模数）。
2. 现在：
   • 通用性：新算法像是一个全地形越野车，不管路面是沥青（质数）还是泥土（非质数），都能跑。
   • 速度：它利用了计算机硬件最擅长的“大数字加法”和“位移”操作，就像给车装上了涡轮增压。
   • 应用：这意味着未来的加密通信、区块链交易、安全认证等需要大量数学运算的场景，会变得更快、更省电、更高效。

一句话总结：
这篇论文发明了一种更聪明、更通用的方法，利用计算机最擅长的“大数加法”和“进位”原理，让计算机在寻找“数字倒数”这件事上，从“步行”升级到了“高铁”速度，而且不再受限于特定的数字类型。

技术摘要

这是一份关于论文《On the Inversion Modulo a Power of an Integer》（整数幂模逆运算）的详细技术总结，内容涵盖问题背景、方法论、核心贡献、实验结果及意义。

1. 研究问题 (Problem)

在现代计算、密码学（如 RSA、椭圆曲线密码、后量子密码）及同态加密中，模逆运算（Modular Inverse）是基础且关键的算术操作。具体而言，给定整数 $a$ 和模数 $N$，寻找 $x$ 使得 $ax \equiv 1 \pmod N$。

本文主要关注以下两类特定场景的模逆计算：

1. 任意整数幂模逆：计算 $x = a^{-1} \pmod{n^k}$，其中 $n > 1$ 是任意整数，$k > 0$。
2. 特定形式的幂模逆：计算 $x = a^{-1} \pmod{n^{2^s}}$，特别是当模数为素数幂 $p^{2^s}$ 时，现有的基于 Hensel 提升（Hensel Lifting）的方法（如 Dumas 和 Hurchalla 的算法）非常高效，但仅限于素数底数。

现有挑战：

• 传统的扩展欧几里得算法或 Montgomery 归约在某些场景下效率不够高。
• Ko¸c 提出了一种针对素数幂 $p^k$ 的高效算法（仅使用加减和移位），但无法直接推广到任意整数底数 $n$。
• Hurchalla 的算法针对 $2^{2^s}$形式极其高效，但缺乏对一般底数$n$ 的推广。
• 如何利用计算机架构的内置算术特性（如 64 位或 128 位字长）来进一步优化计算速度。

2. 方法论 (Methodology)

本文提出了两部分主要的方法论：

第一部分：基于“竖式乘法”思想的通用算法 (Algorithm 3.1)

• 核心思想：受小学算术中竖式乘法（Schoolbook Multiplication）的启发。作者将 $ax \equiv 1 \pmod{n^k}$ 视为一个进位（Carry）问题。
• 推导过程：
  • 设 $a$ 和 $x$ 的 $n$ 进制表示分别为 $a = \sum a_i n^i$ 和 $x = \sum X_i n^i$。
  • 通过模拟乘法过程，分析进位 $q_i$ 的递推关系。
  • 定义辅助变量 $T_i$（与进位相关），推导出简单的线性递推公式：
    $$T_{i+1} = T_i + \frac{a X_i}{n}$$
    $$X_i = -c \cdot T_i \pmod n$$
    其中 $c = a^{-1} \pmod n$ 是初始逆元。
• 特点：
  • 通用性：适用于任意整数 $n > 1$（只要 $\gcd(a, n)=1$）。
  • 操作简便：每一步主要涉及加法、乘法和除以 $n$（右移）。
  • 架构优化：特别设计了 $n=2^{64}$ 和 $n=2^{128}$ 的版本，充分利用 CPU 的 64 位/128 位原生算术指令，避免了大整数库的开销。

第二部分：Hensel 提升方法的推广 (Algorithm 4.1)

• 背景：Dumas 和 Hurchalla 提出了基于 Hensel 提升（类似牛顿迭代法）的算法，用于计算 $a^{-1} \pmod{p^{2^s}}$。
• 推广：
  • 作者通过简单的代数推导，证明了 Hurchalla 的递推关系可以推广到任意底数 $n$，即计算 $a^{-1} \pmod{n^{2^s}}$。
  • 递推公式：$x_{m+1} = x_m(1 + y^{2^m}) \pmod{n^{2^s}}$，其中 $y = 1 - ax_0$。
  • 初始化：提出了针对 $i_0=4$ 情况下的显式初始化公式，仅需位运算（XOR）即可快速获得初始近似值。

第三部分：Ko¸c 算法的替代证明与性质挖掘

• 为 Ko¸c 针对素数幂 $p^k$ 的算法提供了全新的证明。
• 新发现：证明了该算法在计算 $a^{-1} \pmod{p^k}$ 的过程中，实际上同时计算了 $(p^s)^{-1} \pmod a$（即模 $a$ 下 $p$ 的幂的逆元），这是一个有价值的副产品。

3. 关键贡献 (Key Contributions)

1. 提出了通用的模逆算法：打破了以往算法多局限于素数幂或特定形式的限制，实现了针对任意整数底数 $n$ 的 $a^{-1} \pmod{n^k}$ 的高效计算。
2. 利用硬件架构优化：通过选择 $n=2^{64}$ 或 $n=2^{128}$，将大整数运算转化为 CPU 原生的字长运算，显著减少了指令周期。
3. 理论扩展：将 Hurchalla 的高效算法从素数幂 $p^{2^s}$ 成功推广到一般整数幂 $n^{2^s}$，并给出了简洁的代数证明。
4. 算法性质挖掘：揭示了 Ko¸c 算法的“后缀性质”（Suffix Property），即算法中间步骤可直接用于求解 $a^{-1} \pmod{p^s}$ 和 $(p^s)^{-1} \pmod a$。

4. 实验结果 (Results)

作者在 Ubuntu 24.04 系统（AMD Ryzen 7 8845HS 处理器）上进行了实验，对比了以下算法：

• 本文算法 3.1（设置 $n=2^{64}$ 和 $n=2^{128}$）
• Hurchalla 算法（文献 [7]）
• Ko¸c 算法（二进制版本，文献 [8]）

主要发现：

• 性能提升显著：在计算 $a^{-1} \pmod{2^k}$ 时，本文算法（$n=2^{64}$）比 Hurchalla 算法快约 10-20 倍，比 Ko¸c 算法快 数百倍（特别是在 $k$ 较大时）。
  • 例如，当 $k=4096$ 时，本文算法耗时约 7253 ns，而 Ko¸c 算法耗时高达 389,627 ns。
• $n=2^{128}$ 的优势：对于更大的模数，使用 $n=2^{128}$ 作为基数比 $n=2^{64}$ 效率更高，因为每一步处理的位数更多，迭代次数更少。
• 通用性验证：算法在 $n=10$（十进制）等非 2 的幂次底数下也能正确运行，验证了理论的普适性。

5. 意义与影响 (Significance)

• 密码学加速：为现代密码系统（特别是涉及大整数运算的公钥密码和后量子密码）提供了更高效的模逆运算实现方案，有助于降低计算延迟和功耗。
• 算法设计范式：展示了如何从基础的算术原理（如竖式乘法）出发，结合计算机体系结构特性（字长对齐），设计出既通用又高效的算法。
• 理论价值：统一了不同模逆算法的理论框架，揭示了 Ko¸c 算法、Hensel 提升法与代数递推之间的内在联系，为后续研究提供了新的视角。

总结：
本文通过结合初等算术思想与计算机架构特性，提出了一种通用且高效的模逆算法。该算法不仅在理论上推广了现有的素数幂模逆方法，更在实践性能上实现了数量级的提升，特别是在利用 64 位和 128 位原生字长时表现卓越，对高性能计算和密码工程具有重要的应用价值。