求逆元

#求逆元| 来源: 网络整理| 查看: 265

求整数上乘法逆元

求 7 关于 26 的逆元！

扩展欧几里得算法 #include #include //欧几里得函数 void exgcd(int a, int b, int &x, int &y, int &d) { if (!b) { d = a, x = 1, y = 0; } else { exgcd(b, a % b, y, x, d); y -= x * (a / b); } } int inv(int t, int p) { //返回t对p的逆元 int d, x, y; exgcd(t, p, x, y, d); return (x % p + p) % p; //x可能为负，也可能过大 } int main() { int m = 7, n = 26; printf("%d", inv(m, n)); return 0 ; }

或者

#include #include int exgcd(int a,int b,int &x,int &y)//扩展欧几里得算法 { if(b==0) { x=1,y=0; return a; } int ret=exgcd(b,a%b,y,x); y-=a/b*x; return ret; } int getInv(int a,int mod)//求a在mod下的逆元，不存在逆元返回-1 { int x,y; int d=exgcd(a,mod,x,y); return d==1?(x%mod+mod)%mod:-1; } int main() { int m = 7, n = 26; printf("%d", getInv(m, n)); return 0 ; }　

手算　方法1:辗转相除法

求7关于26的逆元，即$7^{-1}$：

设 $7^{-1}$为 X，即7 * X = 1 mod 26 ，求 X 即可

26 / 7 = 3 余 5

7 / 5 = 1 余 2

5 / 2 = 2 余 1

则：

1 = 5 - 2 * 2

1 = 5 - 2 * (7 - 5 * 1) = 3 * 5 - 2 * 7

1 = 3 * (26 - 3 * 7) - 2 * 7= 3 * 26 - 11 * 7

故$7^{-1}$ = -11，由于 -11 不在Z_q中，故$7^{-1}$ = 26 - 11 = 15

方法2

参考：链接

（1）原理

首先对余数进行辗转相除：N = A * a0 + r0A = r0 * a1 + r1r0 = r1 * a2 + r2r1 = r2 * a3 + r3…rn-2 = rn-1 * an + rnrn-1 = rn * an+1 + 0

对上面的商数逆向排列（不含余数为0的商数）：

其中：

b-1 = 1b0 = anbi = an-1 * bi-1 + bi-2商个数为偶数，则bn即为所求的逆元B；商个数为奇数，则N-bn即为所求的逆元B

（2）举例

求7关于26的逆元：

辗转相除法：

26 = 3 * 7 + 5

7 = 1 * 5 + 2

5 = 2 * 2 + 1

因为商的个数为奇数，故 7-1 = 26 - 11 = 15

方法3:Bezout恒等式

（1）原理

用矩阵行初等变换的方法求Bezout，进而求逆元

参考：链接

方法4:扩展欧几里得算法

参考：求逆元算法实现求逆元

代码：

#include using namespace std; //递归求解 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, x, y); int x2 = x, y2 = y; x = y2; y = x2 - (a / b) * y2; return gcd; } //非递归求解 int exgcd01(int a, int b, int& x, int& y) { int x1, y1, x0, y0; x0 = 1; y0 = 0; x1 = 0; y1 = 1; x = 0; y = 1; int r = a % b; int q = (a - r) / b; while (r) { x = x0 - q * x1; y = y0 - q * y1; x0 = x1; y0 = y1; x1 = x; y1 = y; a = b; b = r; r = a % b; q = (a - r) / b; } return b; } int main() { int x, y, a, b,option; cout

【本文地址】

求逆元

求逆元

今日新闻

推荐新闻