密码工程-扩展欧几里得算法
20201331黄文刚
任务详情:
0. 在openEuler(推荐)或Ubuntu或Windows(不推荐)中完成下面任务
- 参考《密码工程》p112伪代码实现ExtendedGCD(int a, int b, int *k, int *u, int *v)算法(5
- 在测试代码中计算74模167的逆。(5
- 自己设计至少两个测试代码。5
- 提交代码和运行结果截图
代码
//myexgcd
#include<stdio.h>
int main()
{
unsigned int a,b;
int u,v,gcd;
int extendedgcd(unsigned int a,unsigned int b,int *x,int *y);
printf("请输入a和b:");
scanf("%d%d",&a,&b);
gcd=extendedgcd(a,b,&u,&v);
printf("u=%d,v=%d\n",u,v);
printf("最大公因子k=%d\n",gcd);
printf("%d*%d+%d*%d=%d\n", u, a, v, b, gcd);
return 0;
}
int extendedgcd(unsigned int a,unsigned int b,int *x,int *y)//扩展欧几里得算法;
{
if(b==0)
{
*x=1;
*y=0;
return a;
}
int ret=extendedgcd(b,a%b,x,y);
int t=*x;
*x=*y;
*y=t-a/b*(*y);
return ret;
}
实现