资源预览内容
第1页 / 共5页
第2页 / 共5页
第3页 / 共5页
第4页 / 共5页
第5页 / 共5页
亲,该文档总共5页全部预览完了,如果喜欢就下载吧!
资源描述
扩展欧几里德算法计算乘法逆元扩展欧几里德算法计算乘法逆元一一欧几里德算法欧几里德算法欧几里德算法又称辗转相除法,用于计算两个整数 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;return 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 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 平台下进行的。六程序运行结果如下:程序运行结果如下:
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号