什么是模幂运算
模幂运算是一种求幂次后的模的计算方法，通常用于计算 \( a^b \bmod c \)，其中 \( a \) 为底数，\( b \) 为指数，\( c \) 为模。这种计算在密码学、数论和计算机科学中非常常见，可以有效地计算大数的幂次模值。
如何计算模幂
计算 \( a^b \bmod c \) 时，直接计算 \( a^b \) 会非常大，因此我们通常使用快速幂算法或模幂算法，逐步将计算规模缩小。下面是快速幂算法的关键步骤：
- 将指数 \( b \) 转换为二进制形式。
- 初始化结果为 1。
- 从指数的最低位（右侧）开始逐位计算，如果该位为 1，则更新结果，新的结果为前一个结果乘以当前的底数值并取模。
- 每次位移操作后，将底数平方并对模 \( c \) 取模，并设为新的底数。
- 重复操作，直到遍历完指数的所有二进制位。
最终得到的结果就是 \( a^b \bmod c \)。
示例
例子 1：计算 \( 5^3 \bmod 13 \)
解答：
将指数 3 转换为二进制，即 \( 3_{10} = 11_2 \)。
初始化：result = 1，底数 = 5，模 = 13。
遍历二进制位（从右到左）：
- 最低位 1：更新结果：result = \( (1 \times 5) \bmod 13 = 5 \)，更新底数：\( (5 \times 5) \bmod 13 = 12 \)
- 最高位 1：更新结果：result = \( (5 \times 12) \bmod 13 = 8 \)
结果：\(5^3 \bmod 13 = 8\)。
例子 2：计算 \( 7^4 \bmod 10 \)
解答：
将指数 4 转换为二进制，即 \( 4_{10} = 100_2 \)。
初始化：result = 1，底数 = 7，模 = 10。
遍历二进制位（从右到左）：
- 最低位 0：不更新 result，更新底数：\( (7 \times 7) \bmod 10 = 9 \)
- 次低位 0：不更新 result，更新底数：\( (9 \times 9) \bmod 10 = 1 \)
- 最高位 1：更新结果：result = \( (1 \times 1) \bmod 10 = 1 \)
结果：\(7^4 \bmod 10 = 1\)。
例子 3：计算 \( 3^{10} \bmod 7 \)
解答：
将指数 10 转换为二进制，即 \( 10_{10} = 1010_2 \)。
初始化：result = 1，底数 = 3，模 = 7。
遍历二进制位（从右到左）：
- 最低位 0：不更新 result，更新底数：\( (3 \times 3) \bmod 7 = 2 \)
- 次低位 1：更新结果：result = \( (1 \times 2) \bmod 7 = 2 \)，更新底数：\( (2 \times 2) \bmod 7 = 4 \)
- 次高位 0：不更新 result，更新底数：\( (4 \times 4) \bmod 7 = 2 \)
- 最高位 1：更新结果：result = \( (2 \times 2) \bmod 7 = 4 \)
结果：\(3^{10} \bmod 7 = 4\)。