密码工程-扩展欧几里得算法

任务详情

0. 在openEuler(推荐)或Ubuntu或Windows(不推荐)中完成下面任务
1. 参考《密码工程》p112伪代码实现ExtendedGCD（int a, int b, int *k, int *u, int *v）算法（5
2. 在测试代码中计算74模167的逆。（5
3. 自己设计至少两个测试代码。5
4. 提交代码和运行结果截图

代码

代码一：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
struct EX_GCD {
    int s;
    int t;
    int gcd;
};
 
struct EX_GCD extended_euclidean(int a, int b) {
    struct EX_GCD ex_gcd;
    if (b == 0) { //b等于0时直接结束求解
        ex_gcd.s = 1;
        ex_gcd.t = 0;
        ex_gcd.gcd = 0;
        return ex_gcd;
    }
    int old_r = a, r = b;
    int old_s = 1, s = 0;
    int old_t = 0, t = 1;
    while (r != 0) { //按扩展欧几里得算法进行循环
        int q = old_r / r;
        int temp = old_r;
        old_r = r;
        r = temp - q * r;
        temp = old_s;
        old_s = s;
        s = temp - q * s;
        temp = old_t;
        old_t = t;
        t = temp - q * t;
    }
    ex_gcd.s = old_s;
    ex_gcd.t = old_t;
    ex_gcd.gcd = old_r;
    return ex_gcd;
    }
 
int main(void) {
    int a, b;
    printf("Please input two integers divided by a space.\n");
    scanf("%d%d", &a, &b);
    if (a < b) { //如果a小于b，则交换a和b以便后续求解
        int temp = a;
        a = b;
        b = temp;
    }
    struct EX_GCD solution = extended_euclidean(a, b);
    printf("%d*%d+%d*%d=%d\n", solution.s, a, solution.t, b, solution.gcd);
     
    return 0;
}

代码二
#include <stdio.h>

void ExtendedGCD(int a, int b, int *k, int *u, int *v) {
    if (b == 0) {
        *k = a;
        *u = 1;
        *v = 0;
    } else {
        ExtendedGCD(b, a % b, k, u, v);
        int temp = *u;
        *u = *v;
        *v = temp - (a / b) * (*v);
    }
}

int main() {
    int a = 1234;
    int b = 5678;
    int k, u, v;
    ExtendedGCD(a, b, &k, &u, &v);
    printf("GCD(%d, %d) = %d\n", a, b, k);
    printf("%d * %d + %d * %d = %d\n", a, u, b, v, k);
    return 0;
}

截图：
代码一的运行截图：

代码二的运行截图：