我想计算a b mod c,其中a
,b
和c
是整数值。有没有有效的方法可以做到这一点?
[pow(a, b) % c
似乎不起作用。
对于此任务,由于多种原因,pow
中定义的<math.h>
功能不是正确的工具:
pow()
函数计算大数可能会溢出double
类型所表示的幅度,并且精度将无法提供模运算所需的低位数字。pow()
可能会为整数参数生成非整数值,将其转换为int
可能会截断为不正确的值。%
操作未在double
类型上定义。一个人应该在一个循环中迭代地计算功率和模量:
unsigned exp_mod(unsigned a, unsigned b, unsigned c) {
unsigned p = 1 % c;
while (b-- > 0) {
p = (unsigned long long)p * a % c;
}
return p;
}
对于b
的非常大的值,迭代将花费很长时间。这是一种有效的幂运算算法,可将时间复杂度从O(b)降低为O(log b):
unsigned exp_mod_fast(unsigned a, unsigned b, unsigned c)) {
unsigned p;
for (p = 1 % c; b > 0; b = b / 2) {
if (b % 2 != 0)
p = (unsigned long long)p * a % c;
a = (unsigned long long)a * a % c;
}
return p;
}
如[rici]所建议,对中间产品使用类型unsigned long long
可以避免较大值a
的幅度问题。对于a
,b
和c
的所有32位值,上述功能应产生正确的结果,但c == 0
除外。[初始步骤p = 1 % c
对于产生0
的结果c == 1 && b == 0
是必要的。显式测试if (c <= 1) return 0;
可能更具可读性,并且可以避免c == 0
上的未定义行为。这是带有特殊情况测试的最终版本,少了一步:
unsigned exp_mod_fast(unsigned a, unsigned b, unsigned c)) {
unsigned p;
if (c <= 1) {
/* return 0 for c == 1, which is the correct result */
/* also return 0 for c == 0, by convention */
return 0;
}
for (p = 1; b > 1; b = b / 2) {
if (b % 2 != 0) {
p = (unsigned long long)p * a % c;
}
a = (unsigned long long)a * a % c;
}
if (b != 0) {
p = (unsigned long long)p * a % c;
}
return p;
}
可在Wikipedia的标题为Modular exponentiation的文章上找到更一般的分析。