快速模幂乘算法详细解释附上示例
时间: 2023-06-09 22:08:06 浏览: 117
快速模幂乘算法可以用于计算 a^b mod m 的值,其中 a, b 和 m 都是正整数。该算法通过将指数 b 转换为二进制形式,利用幂的性质将幂的乘积转化为幂的平方的乘积降低计算复杂度,同时利用模运算的性质降低中间计算的数值大小,从而避免溢出和提高计算效率。
具体步骤如下:
1. 将指数 b 转换为二进制形式,记作 b0b1b2...bn,其中 bi 表示二进制展开中第 i 位的数值;
2. 初始设置计算结果 res = 1,和幂的底数 base = a;
3. 从二进制展开的最高位 n 开始遍历,若该位的值为 1,则将 res 乘上当前的底数 base 并对乘积取模,即 res = (res * base) % m;
4. 将当前底数 base 的值平方并对其进行模运算,即 base = (base * base) % m;
5. 重复步骤 3 和 4 直到遍历完整个二进制展开,此时 res 的值即为 a^b mod m 的结果。
具体理解可以看下面的示例:
假设需要计算 6^13 mod 11 的值,首先将指数 13 转换为二进制形式为 1101,计算过程如下:
b3 = 1,res = 6,base = 6,6 * 6 = 36 = 3 * 11 + 3,res = 6 * 6 = 36 % 11 = 3,base = 6 * 6 = 36 % 11 = 3;
b2 = 0,res = 3,base = 3,3 * 3 = 9,res = 3 * 3 = 9 % 11 = 9,base = 3 * 3 = 9 % 11 = 9;
b1 = 1,res = 9,base = 9,9 * 3 = 27 = 2 * 11 + 5,res = 9 * 9 = 81 % 11 = 4,base = 9 * 9 = 81 % 11 = 4;
b0 = 1,res = 4,base = 4,4 * 4 = 16 = 1 * 11 + 5,res = 4 * 6 = 24 % 11 = 2,base = 4 * 4 = 16 % 11 = 5;
因此,6^13 mod 11 的值为 2。