扩展欧几里德算法计算乘法逆元.doc_第1页
扩展欧几里德算法计算乘法逆元.doc_第2页
扩展欧几里德算法计算乘法逆元.doc_第3页
扩展欧几里德算法计算乘法逆元.doc_第4页
免费预览已结束，剩余1页可下载查看

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

扩展欧几里德算法计算乘法逆元一 欧几里德算法欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。其计算原理依赖于下面的定理： 定理：gcd(a,b) = gcd(b,a mod b)欧几里德算法就是根据这个原理来做的，其算法用C+语言描述为： void swap(int & a, int & b) int c = a a = b; 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 &ar,int &br)int x1,x2,x3;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); coutn最大公约数:rendl; coutn乘法逆元:arendl; coutn乘法逆元:brendl; return 0;四程序分析本程序只是很简单描述了一般情况下的扩展欧几里德算法乘法逆元，当给出的两个数如果最大公因数不为一时，则无乘法逆元，将他们的逆元都设置为0，当给出的数只要有一个为零，则没有乘法逆元。五 序运行环境 本程序采用
人人文库> 全部分类> 应用文书 > 技术指导

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论