如何在 C 中计算整数取幂模常量

Question

我想计算 a^b mod c 其中 a, b 和c 是整数值。有没有有效的方法来做到这一点？

pow(a, b) % c 好像不行。

Answer 1

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

使用 pow() 函数计算大数可能会溢出类型 double 可表示的量级，并且精度将无法提供模运算所需的低位数字。
根据其在 C 库中的实现，pow() 可能会为整数参数生成 non-integral 值，其转换为 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 是为 c == 1 && b == 0 生成结果 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.

的维基百科文章提供了更一般的分析

如何在 C 中计算整数取幂模常量

How can I compute integer exponentiation modulo a constant in C

c

algorithm

math

pow