C语言编程费马小定理推论2.3求模逆元
时间: 2023-09-18 09:05:46 浏览: 72
在C语言中,可以使用扩展欧几里得算法来求模逆元。扩展欧几里得算法可以同时求出最大公约数和两个数之间的一组贝祖等式的系数。
假设要求a关于模m的逆元x,那么可以使用扩展欧几里得算法求出a和m的最大公约数gcd以及一组贝祖等式的系数s和t,使得as + mt = gcd。
如果gcd不为1,则a关于模m不存在逆元。否则,由上式得到as ≡ 1 (mod m),即as mod m = 1。因此,x = s即为a关于模m的逆元。
下面是使用C语言实现求模逆元的代码:
```c
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, y, x);
*y -= a / b * (*x);
return r;
}
int mod_inverse(int a, int m)
{
int x, y;
int g = gcd(a, m, &x, &y);
if (g != 1) {
// a关于模m不存在逆元
return -1;
}
// 注意x可能为负数,需要将结果调整到[0, m)之间
return (x % m + m) % m;
}
```
其中,gcd函数用于求a和m的最大公约数和一组贝祖等式的系数,mod_inverse函数用于求a关于模m的逆元。如果a关于模m不存在逆元,则返回-1。