如何在 C 中以常数为模计算整数幂

Question

我想计算a ^b mod c where a，b并且c是整数值。有没有一种有效的方法来做到这一点？

pow(a, b) % c 似乎不起作用。

Answer 1

对于此任务，由于多种原因，中pow定义的函数<math.h>不是正确的工具：

• 使用该pow()函数计算大数可能会溢出该类型可表示的量值，double并且精度不会提供模运算所需的低位数字。
• 根据其在 C 库中的实现，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和 的所有 32 位值产生正确的结果c，除了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;
}

维基百科文章中提供了更一般的分析，标题为Modular exponentiation。