如何计算C中的常数模的整数幂

问题描述 投票:1回答:1

我想计算a b mod c,其中abc是整数值。有没有有效的方法可以做到这一点?

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

c algorithm math pow
1个回答
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的幅度问题。对于abc的所有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的文章上找到更一般的分析。
© www.soinside.com 2019 - 2024. All rights reserved.