模逆运算快速算法

模逆运算快速算法——扩展的Euclid算法与扩展的Stein算法(1)扩展的Euclid算法求模逆的传统算法是扩展的Euclid算法，该算法是在用Euclid算法求取二个数的最大公因子时，若最大公因子为1，说明二个数互素，则可同时得出二者的乘法逆元。算法描述如下：输入：二个整数a、b，设ba输出：a与b的最大公因子；若二者互素，同时得出乘法逆元Step1:),0,1(),,(321aXXX，),1,0(),,(321NYYYStep2:if03Ythenreturn),gcd(3baX，noinverseStep3:if13Ythenreturn),gcd(3baY，aYbmod21，bbYamod)(11Step4:33YXQStep5:),,(),,(332211321QYXQYXQYXTTTStep6:),,(),,(321321YYYXXXStep7:),,(),,(321321TTTYYYStep8:gotoStep2(2)扩展的Stein算法较之扩展的Euclid算法，扩展的Stein算法可以得到更高的执行效率。Stein算法基于以下求取二个数公因子的基本性质：1)若a与b都是偶数，则)2,2gcd(2),gcd(baba2)若a为偶数、b为奇数，则),2gcd(),gcd(baba3)若a与b都是奇数，则),2)(gcd(),gcd(bbaba由于除2在二进制运算中仅做一次移位操作，因此可以说Stein算法主要只用到了减法，通过计算复杂性分析可知，在最坏情况下，Stein算法所需减法次数为)13()(lbalb。使用扩展的Stein算法处理模逆运算的流程如下图所示。YYYYYNNNNN输出ABymod1结束aA，bB，1x，0y，0'x，1'y2aa2xx2yya，b互换x，'x互换y，'y互换a是偶数？y是偶数？1a？开始0ba？baa'xxx'yyy0y？BxxAyyBxxAyy图处理模逆运算的Stein算法