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

一、模余运算快速算法的描述：

1. 快速幂算法

快速幂算法可以用来快速计算a^b(mod c)的值，其时间复杂度为O(log b)。

具体算法步骤如下：

(1)将b转化为二进制数

(2)从低位到高位逐位处理，如果当前位为1，则将结果乘以a，然后取模；否则，直接将a取平方，然后取模。

(3)重复上述步骤，直到处理完所有位数。

2. 扩展欧几里得算法

扩展欧几里得算法可以用来求解ax + by = gcd(a, b)的一组解(x, y)。

具体算法步骤如下：

(1)若b = 0，则gcd(a, b) = a，此时x = 1，y = 0。

(2)否则，递归调用扩展欧几里得算法，求解出bx' + (a mod b)y' = gcd(b, a mod b)的一组解(x', y')，然后令x = y'，y = x' - (a/b)y'。

二、利用C语言编程实现运算：

1. 计算 2^1000000(mod 77)

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int a = 2, b = 1000000, c = 77;
    int res = 1;
    while (b)
    {
        if (b & 1) res = (res * a) % c;
        a = (a * a) % c;
        b >>= 1;
    }
    printf("2^1000000(mod 77) = %d\n", res);
    return 0;
}

2. 计算 312^13(mod 667)

#include <stdio.h>
#include <stdlib.h>

int exgcd(int a, int b, int *x, int *y)
{
    if (b == 0)
    {
        *x = 1;
        *y = 0;
        return a;
    }
    int gcd = exgcd(b, a % b, y, x);
    *y -= (a / b) * (*x);
    return gcd;
}

int main()
{
    int a = 312, b = 13, c = 667;
    int res = 1;
    while (b)
    {
        if (b & 1) 
        {
            int x, y;
            exgcd(a, c, &x, &y);
            res = (res * x * a) % c;
        }
        a = (a * a) % c;
        b >>= 1;
    }
    printf("312^13(mod 667) = %d\n", res);
    return 0;
}