模余运算快速算法 - C语言实现

模余运算快速算法 - C语言实现

模余运算在密码学、数论等领域有着广泛应用。本文介绍两种常用的模余运算快速算法，并提供 C语言代码示例：

1. 快速幂算法：利用二进制形式快速计算幂运算结果，并将中间结果不断取模，避免溢出。

代码示例：

int mod_pow(int base, int exp, int mod) {
    int res = 1;
    while (exp > 0) {
        if (exp & 1) {
            res = (res * base) % mod;
        }
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}

int main() {
    int ans = mod_pow(2, 1000000, 77);
    printf("%d", ans);
    return 0;
}

2. 扩展欧几里得算法结合快速幂算法：将指数拆分成多个2的次幂的和，利用快速幂算法计算每个2的次幂的结果，再利用扩展欧几里得算法求逆元，最后将所有结果相乘并取模。

代码示例：

int mod_pow(int base, int exp, int mod) {
    int res = 1;
    while (exp > 0) {
        if (exp & 1) {
            res = (res * base) % mod;
        }
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}

int mod_inverse(int a, int mod) {
    int x1 = 1, x2 = 0, x3 = mod;
    int y1 = 0, y2 = 1, y3 = a;
    int q, t1, t2, t3;
    while (y3 != 1 && y3 != 0) {
        q = x3 / y3;
        t1 = x1 - q * y1;
        t2 = x2 - q * y2;
        t3 = x3 - q * y3;
        x1 = y1;
        x2 = y2;
        x3 = y3;
        y1 = t1;
        y2 = t2;
        y3 = t3;
    }
    if (y3 == 0) {
        printf("Error: %d has no inverse modulo %d", a, mod);
        return 0;
    }
    if (y2 < 0) {
        y2 += mod;
    }
    return y2;
}

int mod_mul(int a, int b, int mod) {
    int res = 0;
    while (b > 0) {
        if (b & 1) {
            res = (res + a) % mod;
        }
        a = (a << 1) % mod;
        b >>= 1;
    }
    return res;
}

int mod_pow_multi(int base, int exp[], int exp_len, int mod) {
    int res = 1;
    for (int i = 0; i < exp_len; i++) {
        int tmp = mod_pow(base, exp[i], mod);
        int inv = mod_inverse(tmp, mod);
        res = mod_mul(res, inv, mod);
        base = mod_pow(base, 2, mod);
    }
    return res;
}

int main() {
    int exp[] = {2, 2, 2, 2, 2, 2, 1};
    int ans = mod_pow_multi(312, exp, 7, 667);
    printf("%d", ans);
    return 0;
}

本文提供了两种模余运算快速算法的 C语言代码实现，希望能够帮助你更好地理解和应用这些算法。