扩展欧几里德算法计算乘法逆元

《扩展欧几里德算法计算乘法逆元》由会员分享，可在线阅读，更多相关《扩展欧几里德算法计算乘法逆元（5页珍藏版）》请在金锄头文库上搜索。

1、扩展欧几里德算法计算乘法逆元扩展欧几里德算法计算乘法逆元一一欧几里德算法欧几里德算法欧几里德算法又称辗转相除法，用于计算两个整数 a,b 的最大公约数。其计算 原理依赖于下面的定理： 定理：gcd(a,b) = gcd(b,a mod b)欧几里德算法就是根据这个原理来做的，其算法用 C+语言描述为： void swap(int b = c;int gcd(int a,int b)if(0 = a )return b;if( 0 = b)return a;if(a b)swap(a,b);int c;for(c = a % b ; c 0 ; c = a % b)a = b;b = c;ret

2、urn b;二二扩展欧几里德算法乘法逆元扩展欧几里德算法乘法逆元模 P 乘法逆元对于整数 a、p，如果存在整数 b，满足 ab mod p =1，则说，b 是 a 的模 p 乘法逆元。定理：a 存在模 p 的乘法逆元的充要条件是 gcd(a,p) = 1三三扩展欧几里德算法如下：扩展欧几里德算法如下：#include int gcd(int a, int b , int int y1,y2,y3;int t1,t2,t3;int k;if(0 = a)/有一个数为 0，就不存在乘法逆元ar = 0;br = 0;return b;if(0 = b) ar = 0;br = 0 ;return

3、a;x1 = 1;x2 = 0;x3 = a;y1 = 0;y2 = 1;y3 = b;for(t3 = x3 % y3 ; t3 != 0 ; t3 = x3 % y3)k = x3/y3;t2 = x2-k*y2;t1 = x1-k*y1;x1 = y1;x1 = y2;x3 = y3;y1 = t1;y2 = t2;y3 = t3;if( y3 = 1)/有乘法逆元ar = y2;br = x1;return 1;else/公约数不为 1，无乘法逆元ar = 0;br = 0;return y3;int main()int a,b;int ar,br;int r;cina ;cin b ;r = gcd(a,b,ar,br);cout“n 最大公约数:“rendl;cout“n 乘法逆元:“arendl;cout“n 乘法逆元:“brendl;return 0;四程序分析程序分析本程序只是很简单描述了一般情况下的扩展欧几里德算法乘法逆元，当给出的两个数如果 最大公因数不为一时，则无乘法逆元，将他们的逆元都设置为 0，当给出的数只要有一个 为零，则没有乘法逆元。五序运行环境序运行环境本程序采用用 C语言编写，编译，链接，运行都是在 MinGW Developer Studio 平台下进行的。六程序运行结果如下：程序运行结果如下：