求模逆元的几种算法

摘要：基于模乘法逆元的定义、存在条件及其相关定理，首先，对各求模逆元的算法思想和计算过程进行了深入的剖析，并总结了它们各自的运算特点以及它们的局限性所在，最后，依据可计算的复杂性理论和实际所测试的数据，比较了各种算法的执行效率以及它们的使用范围。

关健词：模逆元；扩展欧几里得算法；二进制扩展欧几里得算法；牛顿迭代法；费马小定理

中图分类号：TP301文献标识码：A文章编号：1009-3044(2008)11-20308-03

1 引言

模算术就是用算术表达式模一些非零整数的计算。其数学概念就是是剩余类环。在数论和近世代数中，模算术是一个很重要的概念和方法，而求解模逆元又是模运算中最重要的一个问题。随着计算机网络技术和通信技术的发展，求解模逆元的问题在现代信息密码安全中有着充分的应用和体现。尤其是在现代公钥密码体制中，加密和解密的过程中，都涉及到求逆元的问题。因此，研究求解模逆元的算法问题不仅在代数学上有重要的理论意义，而且在现代密码学方面也有重要的现实意义。

2 模逆元概念及其相关定理

定义若整数a,b,p, 满足a·b≡1(mod p)．则称a为b模p的乘法逆元，即a=b-1mod p．其中，p是模数。

定理1设p是素数，a∈Z,则ap≡a mod p.特别地当gcd(a,p)=1时，

ap-1≡1(mod p)

成立。此定理就是有名的费马小定理。作为代数学和数论学科方面的一个强有力的工具，它在多项式分解和素数检测方面已有广泛地应用。在此，进行适当转换我们可以十分方便地利用它来计算mod p的逆元。即

ap≡a mod p=>a·ap-2≡1mod p.

所以， a-1=ap-2mod p.

因此，在求a mod p逆元时，若p为素数且gcd(a,p)=1时,则可直接利用该定理计算ap-2mod p的大小。其值就是所求的逆元a-1。一般情况下，由于p值较大，其计算烦琐且易出错。但由于计算思想相对简单即先进行幂运算而后再模运算。因此，更一般的做法是：我们可以利用某些数学工具软件(如maple)进行直接计算即可。

定理2 对于a∈{0,1,2,…,p-1}，存在a-1∈{1,2,3,…,p-1}使

a·a-1≡1mod p

充要条件是gcd(a,p)=1.

该定理的证明(此处从略)主要是用了最大公约数的有关性质，其中重要的一个就是，

gcd(a,p)=S·a+t·p(*1)

(*1)式表明，两整数的最大公约数可用整系数线性组合的方式来表示。且当gcd(a,p)=1时,

有 s·a≡1mod p=>a-1=s.

该定理不但给出了一般模p逆元的存在条件，而且也提供了求逆元的一种方法。本文依据模逆元的定义和相关定理，下面依次给出了求模逆元的几种算法。

3 求模逆元的算法

3.1 穷举法求逆元

在a∈{1,2,…,p-1}的集合中，找某元素b,使得a·b≡1mod p成立的最直接方法：逐元素尝试，直至找到符合条件的元素。此方法就是穷举算法。其思想就是依据定义，在特定的集合中，逐一进行验证。算法描述如下,

voidEnA(int a ,intp ,int & inverse=0)// 穷举法求逆元

{ for(int j←1;j

if (a*j % p = =1 ){ inverse←j; break;}

}//若inverse值是零，则表明a模p乘法逆元不存在。否则，inverse即为所求。

3.2 扩展欧几里得方法求逆

欧几里得算法是计算最大公约数的一个方便而又实用的方法。其原理是，重复利用带余除法，直至余数为零时止。其过程可用下面的式子来描述。

gcd(p,a)=(a,r1)=…=gcd(rN-2,rN-1)=rN.

对上式，作适当处理：自后而前，逐次消去rN-1,rN-2,…,r2,r1

可得到一系列整数si,ti使得ri=sia+tip 且有rN=gcd(p,a)=sNa+tNp

上式就是前面提到的最大公约数的一个性质，即两整数的最大公约数可用整系数线性组合的方式计算得到。这种计算相应的系数并通过线性组合的形式求最大公约数的方法，就是扩展欧几里得算法。

关于sN，tN的计算可由下式递归得到（其正确性可用归纳法予以证明，此处从略），

教育信息化\hwl01.tif>

其中，q表示每次辗转相除时所得的商。显然，扩展欧几里得算法是在欧几里得算法的基础上，通过适当的变换处理得到。但比欧几里得算法提供了更多的信息。如当gcd(a,p)=1时，a-1=sN.并且相应的系数都被一一记录下来。相应算法描述如下,

int EEA(int a,int p) //扩展欧几里得算法

{// 初始化

r0←a,r1←p,s0←1,s1←0,t0←0,t1←1,i←1;

while (ri≠0) //迭代计算

{qi←ri-1/ri；ri+1←ri-1%ri；si+1←si-1-qi·si；

ti+1←ti-1-qi·ti；i←i+1;

}

return .ri，si，ti；//其中si即为所求.

}

3.3 二进制扩展欧几里得方法求逆

二进制扩展欧几里得算法是在扩展欧几里得算法的基础上，基于以下性质作了改进。

(1)若a,b都是偶数，则有 gcd(a,b)=2gcd(a/2,b/2 )

(2)若a,是偶数，b是奇数，则有 gcd(a,b)=gcd(a／2,b )

(3)若a,b都是奇数，则有 gcd(a,b)=gcd((a-b)/2,b)

算法描述如下,

int BEEA (int a,int p)//二进制拓展算法

{ if (a==b) return (1,0);

if(both a and b are even) return EEA(a/2,b/2);

if(exactly one of the two,say a is even)

{(si,ti)←EEA(a/2,b);

if(si is even) return (si/s,ti);

else return (si+b)/2,ti-a/2);

}

if(both a and b are odd,say a>b)

{ (si,ti)←EEA((a-b)/2,b);

if (si is even) return (si/2,ti-si/2);

else return ((si+b)/2,ti-(si+a)/2);

}

}

该算法是扩展欧几里得算法的一个变体。它主要是利用了公约数的有关性质并进行适当转换及通过利用移位操作比用除法执行更快的特点对扩展欧几里得算法进行了改进而得到的。

3.4 牛顿迭代法求逆

k=0,1,2,3,… （*2）

(*2)式就是求方程数值解的牛顿迭代公式。其计算过程是从合适的初值开始，依次代入公式就得到一个序列,该序列在迭代过程中会趋向一个稳定值，该值就是所求方程的解。其思想本质，就是用线性化方法去逼近方程的解。为此，我们可以把求a mod pl逆元看作是求方程a·x≡1mod pl的解。故，可通过找到1/x-a=0的一个近似根进行替代。将其代入(*2)得

（*3）

选择合适的初值x0(满足a·x≡1mod p),利用(*3)，就可求形如a mod pl的逆元。算法描述如下：

int NIA(int a,int p,int l)//牛顿迭代法求逆元

{x0←EEA(a,p,temp);//x0:迭代初值

r←log2 l //迭代的次数

for(i←1;i≤r;i++){xi←(2xi-1-a·xi-1 2)modp2i;}

return xr ;

}

4 算法性能分析与比较

4.1 定性分析

穷举法求逆的时间复杂度为O(p)；扩展算法的时间复杂度为O(log(max(a,p)))；二进制扩展算法的时间复杂度为O(log(max(a,p)))，但其中参与运算的常数因子与扩展欧几里得算法中常数因子相比会更小；牛顿迭代法求逆的时间复杂度为O(l·log(p))。其中，p为模数，max(a,p)指取两数之中的大数，l为p的指数次幂。根据复杂度的函数表达式，从理论上可得出结论：随着p,a的增大，穷举法时间消耗增长幅度最大，牛顿迭代法次之，扩展算法有缓慢增加，二进制扩展算法的时间消耗增加将最为缓慢。

4.2 定量比较

为了便于比较各求模逆元算法的时间开销情况，通过实际测试，我们在下表中列出了相应的测试结果。具体操作环境是，WinXP操作系统，Visual C++6.0,Pentium(R)4 CPU 1.8GHz, 256MB内存。

各求模逆元算法的时间开销对比表

注：（1）重复次数是指执行算法函数的次数；

（2）平均时间是指每次运行算法函数所消耗的时间。

5 结束语

理论分析和实际的数据测试表明：扩展欧几里得算法是求逆元的基本算法,二进制扩展算法是最优的一种算法。在模数较小的情况下用穷举法也是可行的。注意牛顿迭代法以求解方程的方法计算逆元的思想是相比于其它算法是个不错的方法。但由于在计算过程中，含有较多的乘法和除法运算，致使其时间消耗较多。另外，根据实际情况利用费马小定理(借助某些工具软件)进行快速地求解和验证也是一个很便利的方法。

参考文献：

[1] J von zur Gathen,J Gerhard.Modern Computer Algebra[M].北京:世界图书出版公司,2001.

[2] (美)Michael T Goodrich,RobertoTamassia.霍红卫,译.算法分析与设计[M].北京:人民邮电出版社,2006.

[3] (美)萨尼(Sahni S).汪诗林,等,译.数据结构、算法与应用[M].北京:机械工业出版社,2000.

注：本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文

推荐访问： 几种 算法 求模逆元

---