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

Question

我想计算 ab mod c 哪里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 的所有 32 位值产生正确的结果。 , b和 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 提供了更一般的分析。 .