C++ 程序实现模幂运算算法

模幂运算是数论和密码学中一个基本算法，它能有效地找到一个整数的幂次方再除以另一个整数的余数。该算法在处理大数时非常高效，例如在密码学应用中，RSA 加密就是一个例子。

该算法利用了 (a.b) mod n 等价于 (a mod n ⋅ b mod n) mod n 的事实，因此，在幂运算过程中，我们可以在每一步执行模规约以避免巨大的中间结果。

数学概念

模算术

模算术是数论的一个分支，致力于对受模数限制的整数进行算术运算。在模幂运算中，它关注的是模运算，记作 a mod n，表示 a 除以 n 的余数。

模算术的关键性质

加法： (a+b) mod n = ((a mod n) + (b mod n)) mod n。

乘法： (a.b) mod n = (((a mod n) ⋅ (b.mod n)) mod n) mod n。

幂运算

模幂运算问题涉及在给定整数 a、b 和 n 的情况下，高效地推导出 a^b mod n。

方法一：模幂运算的基本迭代方法

模幂运算的基本迭代算法是基本迭代方法。它有一个循环，在每一步迭代地对底数进行平方并对结果进行模 n 规约。这种方法的优点在于其简单性和可理解性，但最重要的是，这种方法是教育领域相关概念的理想选择，并且是理解更高级算法的基础。

程序

输出

Enter the base: 4
Enter the exponent: 3
Enter the modulus: 2
Result: 4^3 mod 2 = 0

说明

算法从将最终结果设置为 1 开始，因为任何数次的 0 幂都是 1。之后，它立即进入一个循环，遍历指数的位。此循环一直持续到指数变为 0。

在循环内

• 检查指数位

它检查以下情况：如果 (exponent % 2 == 1)，以确保指数的当前最低位已设置 (1)。如果该位已设置，则表示相应的 2 的幂是最终结果之一，并且底数乘以当前最终结果。

• 对底数进行平方

为了处理指数中的下一位，对底数进行平方。这是一个关键优化，因为它使算法能够成功地计算 2 的幂。

• 将指数右移

在循环的下一轮中，指数右移，此操作等效于除以 2。

此过程持续到指数等于零。最终，函数返回计算出的值。

主函数中会提示用户输入底数、响应和模数。然后，这些值用于使用幂函数执行模表达式，并显示结果。

示例用法

主函数中示例的使用演示了模幂算法的简单用法和实用性。然而，应该注意的是，这种简单的迭代方法一点也不复杂，但在大数应用中，通常会使用更优化的二元指数方法来提高效率。

复杂性分析

最后，作为使用模幂运算的简单迭代方法编码的 C++ 代码，其时间和空间复杂度是一个宝贵的评估其计算效率和可伸缩性的标准。

时间复杂度

指数二进制表示中的位数可以确定为基于循环迭代次数的模幂运算算法时间复杂度的决定因素。设指数中的位数为 k。

循环迭代

power 函数中的 while 循环对指数的每一位迭代一次。指数在每次迭代中都会右移（除以 D），直到它达到零，因此循环执行 O(k) 次。

循环内的操作

循环执行简单的算术运算，例如，在每次迭代中进行模乘和除以 2。这些操作在每次迭代中都不会停止。

这意味着模幂运算的基本迭代方案的总时间复杂度为 O(k)，其中 k 表示指数的位。这种复杂度被证明是高效的，它不仅使算法能够处理显著大小的指数，而且还使用完成任务所需的合理资源量。

空间复杂度

空间复杂度是对算法运行所需的内存的评估，包括辅助空间和输入空间。

辅助空间

该算法需要常数辅助空间，独立于输入的大小。结果、底数、指数和模数是唯一占用空间变量，每个变量都需要恒定量的存储空间。

输入空间

输入空间由输入值的大小决定：底数、指数和模数。因为这些值由用户输入，不取决于输入的大小。

因此，模幂运算的基本迭代方法的总空间复杂度为 O(1)，表明该算法使用恒定量的内存。