任务要求
- 在openEuler(推荐)或Ubuntu或Windows(不推荐)中完成下面任务，要用git记录实现过程，git commit不能低于5次
- 严格按照《密码工程》p112伪代码实现ExtendedGCD（int a, int b, int *k, int *u, int *v）算法（10')
2.根据ExtendedGCD 实现计算有限域模除的函数int ModDiv(int a, int b, int m) ，返回a/b%m（3‘） - 在测试代码中计算5/ 2% 13。自己再设计至少两个类似测试代码。（2’）
- 提交代码和运行结果截图，git log截图
- 提交使用Markdown并转为pdf格式，或者使用doc、docx格式
任务内容
1、extendedgcd.c
点击查看代码
#include <stdio.h>
// 函数原型
int ExtendedGCD(int a, int b, int *k, int *u, int *v);
int main() {
int a, b, gcd, u, v;
printf("Enter two integers a and b: ");
scanf("%d %d", &a, &b);
gcd = ExtendedGCD(a, b, &u, &v, NULL);
printf("gcd(%d, %d) = %d\n", a, b, gcd);
printf("u = %d, v = %d\n", u, v);
return 0;
}
// Extended GCD 实现
int ExtendedGCD(int a, int b, int *k, int *u, int *v) {
if (b == 0) {
*k = a;
*u = 1;
*v = 0;
return a;
}
int x, y, gcd;
gcd = ExtendedGCD(b, a % b, &x, &y, NULL);
*u = y;
*v = x - (a / b) * y;
if (k != NULL) {
*k = gcd;
}
return gcd;
}
点击查看代码
#include <stdio.h>
// 扩展欧几里得算法
int ExtendedGCD(int a, int b, int *x, int *y);
// 计算模逆元
int ModInverse(int a, int m) {
int x, y;
int g = ExtendedGCD(a, m, &x, &y);
if (g != 1) {
// 如果gcd(a, m)不为1，则a没有模逆元
return -1;
} else {
// 将x转换为正数
x = (x % m + m) % m;
return x;
}
}
// 计算有限域中的除法
int ModDiv(int a, int b, int m) {
int inv = ModInverse(b, m);
if (inv == -1) {
// 如果没有模逆元，返回错误代码或抛出异常
printf("b has no modular inverse.\n");
return -1;
}
return (a * inv) % m;
}
// 扩展欧几里得算法实现
int ExtendedGCD(int a, int b, int *x, int *y) {
if (b == 0) {
*x = 1;
*y = 0;
return a;
}
int x1, y1;
int gcd = ExtendedGCD(b, a % b, &x1, &y1);
*x = y1;
*y = x1 - (a / b) * y1;
return gcd;
}
int main() {
int a, b, m, result;
printf("Enter a, b, and m: ");
scanf("%d %d %d", &a, &b, &m);
result = ModDiv(a, b, m);
if (result != -1) {
printf("(%d / %d) %% %d = %d\n", a, b, m, result);
}
return 0;
}
