模逆运算快速算法.doc

《模逆运算快速算法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、模逆运算快速算法——扩展的Euclid算法与扩展的Stein算法(1)扩展的Euclid算法求模逆的传统算法是扩展的Euclid算法，该算法是在用Euclid算法求取二个数的最大公因子时，若最大公因子为1，说明二个数互素，则可同时得出二者的乘法逆元。算法描述如下：输入：二个整数、，设输出：与的最大公因子；若二者互素，同时得出乘法逆元Step1:，Step2:ifthenreturn，noinverseStep3:ifthenreturn，，Step4:Step5:Step6:Step7:Step8:g

2、otoStep2(2)扩展的Stein算法较之扩展的Euclid算法，扩展的Stein算法可以得到更高的执行效率。Stein算法基于以下求取二个数公因子的基本性质：1)若与都是偶数，则2)若为偶数、为奇数，则3)若与都是奇数，则由于除2在二进制运算中仅做一次移位操作，因此可以说Stein算法主要只用到了减法，通过计算复杂性分析可知，在最坏情况下，Stein算法所需减法次数为。使用扩展的Stein算法处理模逆运算的流程如下图所示。YYYYYNNNNN输出结束，，，，，，互换，互换，互换是偶数？是偶数？？

3、开始？？图处理模逆运算的Stein算法