模指数运算c语言实现

在C语言中，模指数运算通常是指计算一个数的幂并取余数的操作，这在密码学和数学中很常见，尤其是在处理大整数时。由于直接对大整数进行幂运算可能会导致溢出，因此可以使用一种称为“快速幂算法”（Fast Exponentiation Algorithm）的方法，它通过分治策略有效地减少计算次数。

以下是C语言实现模指数运算的一个简单版本：

#include <stdio.h>

// 使用快速幂法计算 a^b mod m 的结果
int powerMod(int a, int b, int m) {
    int result = 1;
    while (b > 0) {
        // 如果b为偶数，则a自乘并除以m
        if (b % 2 == 0) {
            a = (a * a) % m;
            b /= 2;
        }
        // 如果b为奇数，则a乘上当前结果并取模
        else {
            result = (result * a) % m;
            b--;
        }
    }
    return result;
}

int main() {
    int base = 5;  // 基数
    int exponent = 1000000007;  // 指数
    int modulus = 1000000009;  // 余数

    printf("Result of (%d)^%d mod %d is: %d\n", base, exponent, modulus, powerMod(base, exponent, modulus));
    return 0;
}

在这个例子中，`powerMod`函数实现了快速幂算法，将指数b分为二进制表示，每次计算a的一半次方，直到b为0。这种方法大大减少了需要执行的乘法操作次数。