资源描述：
《求模逆元的几种算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、计算机教学与教育信息化本栏目责任编辑:王力求模逆元的几种算法121黄伟亮,王震,黄勇(1.广州大学教育软件研究所,广东广州510006;2.河南大学数学与信息科学学院,河南开封475001)摘要:基于模乘法逆元的定义、存在条件及其相关定理,首先,对各求模逆元的算法思想和计算过程进行了深入的剖析,并总结了它们各自的运算特点以及它们的局限性所在,最后,依据可计算的复杂性理论和实际所测试的数据,比较了各种算法的执行效率以及它们的使用范围。关健词:模逆元;扩展欧几里得算法;二进制扩展欧几里得算法;牛顿迭代法;费马小定理中图分类号:TP301文献标识码:A文章编号
2、:1009-3044(2008)11-20308-03SeveralAlgorithmstoSolveModularInversesHUANGWei-liang1,WANGZhen2,HUANGYong1(1.InstituteofEducationalSoftware,GuanzhuoUniversity,Guangzhou510006,China;2.SchoolofMathematicsandInformationSciencesHenanUniversity,Kaifeng475001,China)Abstract:Basedonthedefin
3、ition,theexistentconditionandthecorrelativetheoremofthemodularinverse,thispaperlookeddeepintoseveralalgorithmsaboutfindingthemodularinverse,andsummarizedtheircharacteristicsandlimitations.Thenaccordingtothecostanaly-sistheoryandtheactualtestingdata,theefficiencyandtheapplicationo
4、feachalgorithmwerecompared.Keywords:Modularinverses;ExtendedEuclideanAlgorithm;BinaryExtendedAlgorithm;Newtoniteration;Fermat'slittletheorem1引言模算术就是用算术表达式模一些非零整数的计算。其数学概念就是是剩余类环。在数论和近世代数中,模算术是一个很重要的概念和方法,而求解模逆元又是模运算中最重要的一个问题。随着计算机网络技术和通信技术的发展,求解模逆元的问题在现代信息密码安全中有着充分的应用和体现。尤其是在现代公钥
5、密码体制中,加密和解密的过程中,都涉及到求逆元的问题。因此,研究求解模逆元的算法问题不仅在代数学上有重要的理论意义,而且在现代密码学方面也有重要的现实意义。2模逆元概念及其相关定理定义若整数a,b,p,满足a·b≡1(modp).则称a为b模p的乘法逆元,即a=b-1modp.其中,p是模数。定理1设p是素数,a∈Z,则ap≡amodp.特别地当gcd(a,p)=1时,ap-1≡1(modp)成立。此定理就是有名的费马小定理。作为代数学和数论学科方面的一个强有力的工具,它在多项式分解和素数检测方面已有广泛地应用。在此,进行适当转换我们可以十分方便地利用它
6、来计算modp的逆元。即ap≡amodp=>ap-2·a≡1modp.所以,a-1=ap-2modp.因此,在求amodp逆元时,若p为素数且gcd(a,p)=1时,则可直接利用该定理计算ap-2modp-1。的大小。其值就是所求的逆元a一般情况下,由于p值较大,其计算烦琐且易出错。但由于计算思想相对简单即先进行幂运算而后再模运算。因此,更一般的做法是:我们可以利用某些数学工具软件(如maple)进行直接计算即可。定理2对于a∈{0,1,2,⋯,p-1},存在a-1∈{1,2,3,⋯,p-1}使a-1·a≡1modp充要条件是gcd(a,p)=1.该定理
7、的证明(此处从略)主要是用了最大公约数的有关性质,其中重要的一个就是,gcd(a,p)=S·a+t·p(*1)(*1)式表明,两整数的最大公约数可用整系数线性组合的方式来表示。且当gcd(a,p)=1时,有s·a≡1modp=>a-1=s.该定理不但给出了一般模p逆元的存在条件,而且也提供了求逆元的一种方法。本文依据模逆元的定义和相关定理,下面依次给出了求模逆元的几种算法。3求模逆元的算法3.1穷举法求逆元在a∈{1,2,⋯,p-1}的集合中,找某元素b,使得a·b≡1modp成立的最直接方法:逐元素尝试,直至找到符合条件的元素。此方法就是穷举算法。其思
8、想就是依据定义,在特定的集合中,逐一进行验证。算法描述如下,voidEnA(in
