首页c语言EXGCD求乘法逆元

c语言EXGCD求乘法逆元

时间: 2024-03-13 08:38:32 浏览: 162

在数学中，如果a和n是整数，且它们互质，那么a对于模n的乘法逆元是一个整数x，满足ax ≡ 1 (mod n)。在C语言中，可以使用扩展欧几里得算法（EXGCD）来求解乘法逆元。EXGCD可以求出最大公约数以及满足等式mx+ny=gcd(m,n)的一组(x,y)。如果a和n互质，那么ax+ny=1，其中x就是a对于模n的乘法逆元。因此，我们可以使用EXGCD来求解a对于模n的乘法逆元。具体实现方法如下： 1. 定义一个函数exgcd，输入参数为a、b、x、y，输出参数为最大公约数gcd和满足等式mx+ny=gcd(m,n)的一组(x,y)。 2. 在函数中，首先判断b是否为0，如果为0，则返回a作为最大公约数，同时将x赋值为1，y赋值为0。 3. 如果b不为0，则递归调用exgcd函数，输入参数为b、a%b、y、x-a/b*y，输出参数为gcd和一组(x,y)。 4. 最后返回gcd作为a对于模b的乘法逆元。下面是C语言代码实现： ``` int exgcd(int a, int b, int &x, int &y) { if (b == 0) { x = 1; y = 0; return a; } int gcd = exgcd(b, a % b, y, x - a / b * y); return gcd; } int mod_inverse(int a, int n) { int x, y; int gcd = exgcd(a, n, x, y); if (gcd != 1) { // a和n不互质，不存在乘法逆元 return -1; } else { // 返回a对于模n的乘法逆元 return (x % n + n) % n; } } ```

阅读全文