模余运算1计算2^1000000mod 772计算312^13mod667要求：一 模余运算快速算法的描述; 二 利用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;