用c语言实现扩展欧几里德算法求模逆元
时间: 2023-10-21 18:07:11 浏览: 45
扩展欧几里德算法求模逆元可以用来解决一类问题,即对于给定的整数a和模数m,求出一个整数x使得ax ≡ 1 (mod m)。下面是用C语言实现扩展欧几里德算法求模逆元的代码:
```c
#include <stdio.h>
// 求最大公约数
int gcd(int a, int b, int *x, int *y)
{
if (b == 0) {
*x = 1;
*y = 0;
return a;
}
int r = gcd(b, a % b, x, y);
int t = *x;
*x = *y;
*y = t - a / b * *y;
return r;
}
// 求模逆元
int mod_inv(int a, int m)
{
int x, y;
int g = gcd(a, m, &x, &y);
if (g != 1) {
printf("No solution!\n");
return -1;
} else {
return (x % m + m) % m;
}
}
// 测试
int main()
{
int a = 5, m = 7;
int inv = mod_inv(a, m);
if (inv >= 0) {
printf("%d 的模 %d 逆元是 %d\n", a, m, inv);
}
return 0;
}
```
在上面的代码中,我们首先定义了一个函数`gcd`,用来求解最大公约数。这个函数的输入参数包括两个整数a和b,以及两个指向整数的指针x和y。函数返回值是a和b的最大公约数。在函数中,我们采用了递归的方式来求解最大公约数,并利用指针x和y保存了扩展欧几里德算法中每次迭代后的结果。
接下来,我们定义了一个函数`mod_inv`,用来求解模逆元。这个函数的输入参数包括两个整数a和m,表示要求解的模逆元是a关于模数m的逆元。函数返回值是a关于模数m的逆元,如果不存在,则返回-1。在函数中,我们首先调用了函数`gcd`来求解a和m的最大公约数,并利用指针x和y保存了扩展欧几里德算法中每次迭代后的结果。如果a和m的最大公约数不为1,则说明不存在模逆元,函数返回-1。否则,我们利用扩展欧几里德算法的结果来计算模逆元,并返回结果。
最后,在主函数中,我们定义了两个整数a和m,并调用函数`mod_inv`来求解a关于模数m的逆元。如果求解成功,则输出结果,否则输出错误信息。