欢迎来到天天文库
浏览记录
ID：1513490
大小：405.50 KB
页数：8页
时间：2017-11-12
《辗转相除法求模的逆元》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、辗转相除法求模的逆元问题：求A关于模N的逆元B，即要找出整数B，使A×BmodN＝1(或A×B＝x×N＋1)，这里要求A和N互素。方法：辗转相除法（即欧几里德算法）该算法原用于求两个数的最大公约数，经过变形可用于求模逆元辗转相除法求模的逆元首先对余数进行辗转相除：N＝A×a0＋r0A＝r0×a1＋r1r0＝r1×a2＋r2r1＝r2×a3＋r3……rn-2＝rn-1×an＋rnrn-1＝rn-2×an+1＋0辗转相除法求模的逆元对上面的商数逆向排列(不含余数为0的商数)：其中：b-1＝1b0＝anbi＝an-i×bi-1＋bi-2如果n为奇数(即商数个数为偶数)，则
2、bn即为所求的逆元B；如果n为偶数(即商数个数为奇数)，则N－bn即为所求的逆元B。辗转相除法求模的逆元例1：求61关于模105的逆，先对余数辗转相除：105＝61×1＋4461＝44×1＋1744＝17×2＋1017＝10×1＋710＝7×1＋37＝3×2＋13＝3×1＋0辗转相除法求模的逆元将商数逆序排列：由于商数个数为偶数，因此31即为61关于模105的逆元。(31×61＝105×18＋1)辗转相除法求模的逆元例2：求31关于模105的逆，先对余数辗转相除：105＝31×3＋1231＝12×2＋712＝7×1＋57＝5×1＋25＝2×2＋12＝1×2＋0辗转相
3、除法求模的逆元将商数逆序排列：由于商数个数为奇数，因此105-44=61即为31关于模105的逆元。辗转相除法求模的逆元练习1：求19关于模210的逆练习2：求191关于模210的逆
此文档下载收益归作者所有
