C++ 中的模逆元

引言

在计算机科学和数学的各个领域，模运算是一个非常重要的概念。模乘逆元是其核心概念之一。在本文中，我们将探讨模乘逆元是什么，它为什么重要，以及如何使用 C++ 有效地计算它。

问题陈述

我们希望找到一个整数 x，使得 (a * x) % m = 1，其中给定了两个整数 a 和 m。换句话说，我们正在寻找一个 x 值，当它与 a 相乘然后除以 m 时，余数为 1。

• 理解模运算

在深入研究模乘逆元之前，让我们简要回顾一下模运算。我们在 模运算中使用余数。例如，在模 5 运算中，7 mod 5 是 2，因为 7 除以 5 后只剩下 2。

• 模乘逆元的重要性

密码学尤其依赖于模乘逆元的存在，而数论在其运算中（包括处理模运算的算法）大量应用模乘逆元。例如，在 RSA 加密过程中，解密密钥就是使用模乘逆元计算的。

• 计算模乘逆元

有许多计算模乘逆元的方法，例如 **扩展欧几里得算法** 和 **费马小定理**。但是，我们在 C++ 中重点介绍扩展欧几里得算法的使用。

模乘逆元的特点

C++ 中的模乘逆元具有一些特点。此函数的一些主要特点如下：

• 它计算数字 a 模 m 的模乘逆元，主要用于数论、密码学、计算和其他数学应用。
• 扩展欧几里得算法：该算法使用扩展欧几里得算法找到两个整数 a 和 m 的最大公约数 (GCD)，以及满足 a*x + m*y = gcd 的 x 和 y。
• 高效的时间复杂度：该算法的时间复杂度相对于给定的 a 和 m 值是 **对数** 的，这使其对于大数非常高效。通过递归地分割输入值，该算法需要最少的操作，从而实现这种简洁性。
• 空间效率：该算法的空间复杂度与其时间复杂度相匹配，主要需要存储输入的空间、递归变量以及临时变量和系数。因此，这种空间使用是高效的，并且不随输入大小的增加而直接增加。
• 错误处理：此程序的错误处理部分检查是否存在模乘逆元。如果 'a' 和 'm' 的 GCD 结果为 1（表示它们不互质），则不存在模乘逆元。因此，此类算法应输出适当的错误指示符。
• 可用性和可扩展性：该算法设计为 C++ 函数，这使得它可以在需要模运算的更大程序或项目中重用和集成。它将以模块化和结构化的方式工作，以提高可读性和可维护性。
• 在 main 函数中的演示：代码包含一个 main 函数，展示了如何使用一些示例输入来使用模乘逆元函数。它提供了一个如何使用该算法、它的作用以及它的输出样子的示例。

历史

• 古老根源：古代巴比伦人和埃及人（公元前 3000 年 - 公元前 500 年）：这些文明接触了算术等早期数学元素。虽然他们今天没有具体处理模运算或拥有乘法逆元概念，但他们的贡献为数学的早期发展奠定了基础。
• 古希腊数学家（约公元前 600 年 - 公元前 300 年）：有像 **欧几里得** 和 **丢番图** 这样的数学家，他们对数论做出了重大贡献，尤其是在模运算方面。欧几里得求最大公约数 (GCD) 的算法与计算模乘逆元时使用的扩展欧几里得算法 EEA 密切相关。
• 费马和欧拉（17-18 世纪）：数论也由 **皮埃尔·德·费马、莱昂哈德·欧拉** 等人发展。对模运算的理解依赖于费马小定理和欧拉的欧拉函数。
• 20 世纪至今：密码学强调了模运算和逆元的重要性，它们与计算机科学一起被发明出来。RSA 加密就是一个例子，其中计算模乘逆元的算法在加密/解密技术中找到了实际应用。
• 高效算法的发展：随着时间的推移，数学家和计算机科学家不断优化数学技术（如扩展欧几里得算法）以及其他变体，以提高计算效率，同时开发用于计算模乘逆元的算法。
• 密码学、计算机科学和数学：如今，模运算及其逆元在密码学、计算机科学、数论和算法设计等各个领域都发挥着至关重要的作用。它们构成了安全通信协议、加密系统和数学算法的基础。

程序 1

让我们举一个例子来说明 C++ 中的 **模乘逆元**。

输出

The modular multiplicative inverse of 7 mod 11 is 8

说明

1. 输入参数：此示例接受两个整数 a 和 m，其中 a 是我们要查找其逆数的数字，m 是模数。
2. 使用扩展欧几里得算法：接下来，使用扩展欧几里得算法找到 a 和 m 的 GCD 以及系数 x 和 y，使得 a*x + m*y = gcd。
3. 检查是否存在：如果 a 和 m 的 GCD ≠ 1，则不存在模乘逆元，因为它们不互质（即，它们除了 1 之外还有一个公因子）。
4. 计算逆元：相反，如果 GCD 等于 1（a 与 m 互质），则 x 可以称为 a 模 m 的模乘逆元。但是，应注意 x 需要为正且在 m 的范围内，以便我们将 m 应用于 x，但如果需要，可以添加它的另一个实例，其绝对值等于 m，使其为正。

时间和空间复杂度

时间复杂度

• 总的来说，用于获得模乘逆元的扩展欧几里得算法的时间复杂度是高效的。它大约需要 O(log(min(a,m)))，其中 a 和 m 是输入整数。
• 扩展欧几里得算法具有递归调用，用于计算 GCD 和系数 x 和 y。每次调用都会将涉及的数字减半，从而产生对数时间复杂度。但是，操作次数的确切数量取决于给定的输入和具体的实现细节。

空间复杂度

• 该算法的空间复杂度也很高效。它主要需要空间来存储计算中使用的变量，例如输入整数 a 和 m、系数 x 和 y，以及递归调用期间使用的临时变量。
• 由于该算法使用递归，因此递归堆的最大深度决定了空间复杂度。对于扩展欧几里得算法，递归深度也大约为 O(log(min(a,m)))，与时间复杂度相匹配。

程序 2

让我们再举一个例子来说明 C++ 中的 **模乘逆元**。

输出

Shortest distances from source node 0:
Node 0: 0
Node 1: 5
Node 2: 3
Node 3: 10
Node 4: 7
Node 5: 5

说明

1. 使用的数据结构

• Edge 结构：它表示图中的一条边，包含目标节点 (to) 和边的权重 (weight)。
• 优先队列：它用于根据节点与源节点的距离来优先处理节点。
• 函数：void dijkstra(vector<vector<Edge>>& graph, int source, vector<int>& distance)

2. 输入参数

• graph：以邻接表表示的图，其中 graph[u] 包含从节点 u 出发的所有边。
• source：它是从中计算距离的源节点的索引。
• distance：一个向量，用于存储从源节点到图中每个节点的最短距离。

3. 算法

• 它使用最大值初始化距离向量，但源节点除外 (distance[source] = 0)。
• 接下来，初始化一个优先队列 (pq) 来存储距离和节点索引的对，最初包含源节点 ({0, source})。
• 重复直到 pq 为空
• 从优先队列中弹出顶部元素 ({dist_u, u})。
• 如果到 u 的距离大于存储的距离，则跳过此迭代（优化步骤）。
• 遍历节点 u 的所有边 (edge)
• 计算到目标节点 v (distance[u] + weight_uv) 的新距离。
• 如果此新距离短于到 v 的当前距离，则更新 distance[v] 并将 {distance[v], v} 推入 pq。
• 循环结束后，distance 包含从源节点到图中所有其他节点的最短距离。

4. 主函数

• 在 main() 函数中，我们创建了一个包含节点 0 到 5 的示例图，并在节点之间添加了加权边。
• 之后，调用 **dijkstra 函数** 来计算从节点 0（源节点）到所有其他节点的最短距离。
• 输出每个节点到源节点的最短距离。

时间和空间复杂度

• 时间复杂度：O((V+E)logV)
• 空间复杂度：O(V+E)

结论

总之，理解 **模乘逆元** 在各种数学和计算应用中可能很重要，例如密码学和数论。我们可以使用 C++ 扩展欧几里得算法高效地计算模乘逆元，从而解决许多涉及模运算的问题。