求解模逆元問題的擴展歐幾里得算法

求解模逆元問題的擴展歐幾里得算法

解模逆算法是計算機代理中最重要的問題。隨著計算機網(wǎng)絡(luò)技術(shù)和通信技術(shù)的發(fā)展，在通信理論、信息安全、密碼學(xué)等領(lǐng)域應(yīng)用了解模逆算法問題。在ssa公鑰被盜系統(tǒng)中，加密和解密密鑰與模逆代碼操作相關(guān)。此外，在橢圓曲線公鑰密碼系統(tǒng)和數(shù)字簽名系統(tǒng)中，當(dāng)需要選擇模擬結(jié)果表明，模型忽略了隨機操作。因此，研究解模逆元的問題不僅具有重要的理論意義，而且具有很強的現(xiàn)實意義。1求解p-2modp的逆元設(shè)整數(shù)a,x,p滿足a·x≡1modp.則稱x為a模p的乘法逆元,即x=a-1modp.擴展歐幾里得算法是求模逆元的一個重要工具.其基本思想是:利用兩整數(shù)的最大公約數(shù)可用整系數(shù)線性組合的方式表示的性質(zhì),重復(fù)利用帶余除法,并記下相應(yīng)的系數(shù),直至余數(shù)為零時止.其計算過程可用下組式子來描述,{gcd(p,a)=gcd(a,r1)=?=gcd(rN?2,rN?1)=rNri=si?a+ti?p(1≤i≤N)(1){gcd(p,a)=gcd(a,r1)=?=gcd(rΝ-2,rΝ-1)=rΝri=si?a+ti?p(1≤i≤Ν)(1)這里ri為每次相除所得的余數(shù),si,ti為其相應(yīng)的整數(shù)系數(shù).尤其當(dāng)rN=gcd(p,a)=sN·a+tN·p=1.則a-1=sN=(1-tN·p)/a.這里sN就是所求a模p的逆元.對形如ap·x≡1modp(a∈Z,p是質(zhì)數(shù))同余方程,求ap模p的逆元,由費馬小定理,很容易求得其逆元值為a-2modp.但對形如p·x≡1modap的同余方程,欲求p-1modap的值,費馬小定理就不適用了.通常的求解方法是,先計算出ap的值,然后,利用擴展歐幾里得算法或是在其基礎(chǔ)上進(jìn)行某些改進(jìn)而進(jìn)行求解.除此之外,對于該類問題的逆元求解,還有沒有其他的通用的計算方法?更進(jìn)一步,該類問題有沒有類似費馬小定理那樣簡潔的求解逆元的公式?本文的研究工作,就是在這樣的背景下展開的.2費馬小定理與apamodp對于形如p·x≡1modap(a∈Z,p是質(zhì)數(shù))的同余方程,求x(即p-1modap)的問題與ap·x≡1modp(a∈Z,p是質(zhì)數(shù))方程在形式上具有一定的相似性,于是我們很自然地會想到費馬小定理:設(shè)p是素數(shù),a∈Z,則ap≡amodp.特別地當(dāng)gcd(a,p)=1時,ap-1≡1modp,即ap·a-2≡1modp.由模逆元定義知,a-2modp就是ap模p的逆元.由于本文所要求的方程問題與費馬小定理所涉及的內(nèi)容有一定的相似性,所以,本文就從模逆元的存在條件、最大公約數(shù)的整系數(shù)線性組合表示等性質(zhì)方面對該問題進(jìn)行分析和探討,以期找到該類問題的通用求解方法.2.1基于模逆元的同余對任意兩個整數(shù)a,p,a模p存在逆元的充要條件是,gcd(a,p)=1.由費馬小定理可推知,ap·a-2≡1modp,故依據(jù)模逆元的存在條件和同余的性質(zhì)知,gcd(ap,p)=1.即p-1modap一定存在.2.2最大公約數(shù)的性質(zhì)求任意兩整數(shù)最大公約數(shù)的經(jīng)典算法是輾轉(zhuǎn)相除法.其計算過程如式(1)所示,從中可得到最大公約數(shù)的一個重要性質(zhì),即兩整數(shù)的最大公約數(shù)可用整系數(shù)線性組合的形式來表示.因此,當(dāng)時gcd(ap,p)=1時,ap,p這兩個數(shù)的最大公約數(shù)就可用式(2)來表示,gcd(ap,p)=sN·ap+tN·p=1,sN,tN∈Z(2)2.3逆元tn求解p-2modap的逆元法由同余的性質(zhì),可將式(2)兩邊同時模p并移項得,sN·ap≡1modp(3)依據(jù)費馬小定理可知,ap≡amodp.所以,就可直接計算出式(3)中的sN,即sN=a-1modp.因此,把sN代入式(2)可得,tN=(1-sN·ap)/p(4)則tN就是所求的pmodap的逆元解,即tN=p-1modap.綜上所述,對形如p·x≡1modap(a∈Z,p是質(zhì)數(shù))的同余方程,求解p-1modap的問題,可以分為兩個步驟進(jìn)行.首先,求出sN=a-1modp的值;其次,利用式(4)就可直接計算出p-1modap的值,即x=tN=p-1modap=(1-sN·ap)/p.與通常的求模逆元的方法相比,該方法不是首先計算ap(注:ap值可能是大整數(shù)如256、512和1024位的整數(shù)情況)的值,而是先計算a-1modp的大小(通常情況下,a,p都是一個機器整型所表示的2個字節(jié)或4個字節(jié)的整數(shù));其次,就可通過本文所提供的公式直接進(jìn)行計算求解.3p-2modap求解算法的實現(xiàn)依據(jù)上述分析,對方程p·x≡1modap(a∈Z,p是質(zhì)數(shù)),求解p-1modap的問題,主要是先通過轉(zhuǎn)換去計算a-1modp的值,然后,把計算結(jié)果代入求解公式就很容易地求出p-1modap的值.按照這種處理問題的思路,本文給出了相應(yīng)的實現(xiàn)代碼.下面是用VC6.0實現(xiàn)的程序代碼.以上就是我們針對形如p·x≡modap的同余方程定義的求解x的代碼函數(shù),voidSolve_Inverse(inta,intp,CString&strInverse).其使用就是在調(diào)用該函數(shù)時,向其傳遞相應(yīng)的實參,就可得到所需計算結(jié)果的精確表達(dá)式.4計算與測試結(jié)果分析4.1實驗實現(xiàn)和驗證該算法的時間復(fù)雜度為O(log(max(a,p))).根據(jù)復(fù)雜度表達(dá)式,從理論上可得出:隨著a,p(a,p都在一個機器整型所表示的范圍之內(nèi))增大,該算法的時間消耗量的增加幅度變化不是很大,但是在最后的具體數(shù)值計算時,會涉及大整數(shù)的計算,由于VC本身沒提供有關(guān)大整數(shù)運算的代碼模塊,故本文的上述代碼實現(xiàn)部分就只給出了所求逆元的解析表達(dá)式算法.為說明該算法的可靠性和可行性,下面的表1給出了幾個實際的數(shù)據(jù)測試用例,其結(jié)果的準(zhǔn)確性可用第三方的數(shù)學(xué)軟件進(jìn)行驗證(本文用的是Maple數(shù)學(xué)軟件).實驗操作環(huán)境為,WinXP操作系統(tǒng),VisualC++6.0,Maple10.0,Pentium(R)4CPU1.8GHz,256MB內(nèi)存.4.2關(guān)于模數(shù)ap和等價a由表1可以看出,對形如p·x≡modap的同余方程,在求解p-1modap時,用本文給出的方法計算所得結(jié)果都為負(fù)值;而用Maple軟件計算求得的結(jié)果均為正值,且其絕對值的大小均不相同.本小節(jié)將對這兩種不同的結(jié)果進(jìn)行深入地分析和探討.這里,以表中的第一行數(shù)據(jù)為例進(jìn)行分析、比較.此處a=3,p=7.求p-1modap的值,用本文的方法得到的結(jié)果為-1562,用Maple軟件得到的計算結(jié)果為625.進(jìn)一步比較這兩個結(jié)果之間的關(guān)系,可發(fā)現(xiàn)這兩個數(shù)值滿足關(guān)系式,|?1562|+|625|=2187=37|-1562|+|625|=2187=37,即二者的絕對值等于ap很顯然,用本文所給方法計算所得的結(jié)果與用Maple軟件計算所得的結(jié)果對于模數(shù)(ap)而言,是一對符號相反,絕對值之和等于模數(shù)的互補關(guān)系.同理,對其他兩組數(shù)據(jù)進(jìn)行分析、比較,其結(jié)果也都滿足上述互補關(guān)系.更進(jìn)一步,我們對任給定的兩個整數(shù)a,p(不妨假定p>a),依據(jù)模逆元存在條件及最大公約數(shù)可以線性整系數(shù)組合表示的性質(zhì)可知,必存在相應(yīng)的整數(shù)s1,t1使得,gcd(p,a)=s1·a+t1·p=1.這里不妨假設(shè)s1>0,并令s2=s1-p,在該條件下,若存在一個相應(yīng)的整數(shù)t2,使上式成立,就能說明,兩個符號相反,但其絕對值之和等于模數(shù)的這兩個數(shù)都是所求的逆元解.下面把s2=s1-p,代如上式得,s2·a+(t1+a)·p=1顯然,t2=t1+a,因此,s1,s2這兩個符號相反,絕對值之和等與模數(shù)的數(shù),都是符合要求的逆元解.事實上,用本文算法給出的數(shù)值(即負(fù)整數(shù))與用Maple軟件計算所得的數(shù)值(即正整數(shù))都是關(guān)于模數(shù)(ap)的一對互補關(guān)系,即符號相反,絕對值之和等于模數(shù)的關(guān)系.因此,二者在邏輯上是等價的,即用本文提供的算法計算所得到結(jié)果與用Maple計算所得結(jié)果都是符合要求的逆元解.5實際數(shù)據(jù)分析本文給出了求p·x=modap方程解的一個精確的解析表達(dá)公式算法.該算法主要分為兩個步驟:①計算a-1modp;②