模n剩余類環(huán)中的元素可逆和逆元的計(jì)算

模n剩余類環(huán)中的元素可逆和逆元的計(jì)算

0逆元算法的應(yīng)用r.z（n）是模式n的剩余環(huán)，r的元素a是小于n的非負(fù)總數(shù)。a在r中的逆反映是指元素b為r敖的元素b。檢驗(yàn)R中的元素可逆以及計(jì)算可逆元的逆元的算法有廣泛的應(yīng)用(如公鑰密碼制RSA)。傳統(tǒng)的算法是Euclid算法和擴(kuò)展的Euclid算法,時(shí)間復(fù)雜度為O(n3)。如果將n限制在比較窄的范圍,時(shí)間復(fù)雜度就要低得多。本文討論模n=pk剩余類環(huán),其中p是一個(gè)不大的素?cái)?shù)。在這個(gè)環(huán)內(nèi),任何一個(gè)數(shù)a(小于pk的非負(fù)整數(shù))都可以表示為k位p進(jìn)制數(shù),因此可以用k維數(shù)組a[0:k-1]表示,其中a[i](小于p的非負(fù)整數(shù))是a的p進(jìn)制數(shù)的第i位數(shù)字。在文中引入a的階的概念,利用元素的階,筆者設(shè)計(jì)計(jì)算逆元的逐位消除法,并且對(duì)逐位消除法編寫(xiě)程序(C語(yǔ)言)。1該算法1.1被減數(shù)不夠減時(shí)a是r的逆元位置假設(shè)p是一個(gè)不太大的素?cái)?shù),k是大于1的整數(shù),n=pk,R=Z(n)是模n剩余類環(huán)。R的元素是小于n的非負(fù)整數(shù)。將a的元素對(duì)應(yīng)一個(gè)k維數(shù)組a[0;k-1],其中a[i](小于p的非負(fù)整數(shù))是a的p進(jìn)制數(shù)的第i位數(shù)字(從低位到高位)。在R的元素的運(yùn)算中,因?yàn)閚≡0(modn),所以在加法和乘法中,超過(guò)k位的數(shù)應(yīng)刪除;在減法中,被減數(shù)不夠減時(shí),可以從k位借。定理1設(shè)a是R的非0元。a是R的可逆元當(dāng)且僅當(dāng)a≠0。證明:在模n剩余類環(huán)R中,a可逆當(dāng)且僅當(dāng)gcd(c,d)=1。因?yàn)閚=pk,所以n只有一個(gè)素因數(shù)p。因此a是可逆元當(dāng)且僅當(dāng)p不是a的因數(shù)。設(shè)a=qp+r(0≤r<p)。因而a是可逆元當(dāng)且僅當(dāng)r≠0。由于r=a,因此a是可逆元當(dāng)且僅當(dāng)a≠0。定理2設(shè)a是R的可逆的元素,a=x。(1)若x在模p剩余類環(huán)Z(p)中的逆元是y,即xy≡1(modp),令c=ay,則c的p進(jìn)制數(shù)的0位數(shù)c=1。(2)若c在R中的逆元是b,則a在R中的逆元是yb。證明:由于xy≡1(modp),則有整數(shù)k使得xy=kp+1。因?yàn)閍=qp+x,所以ay=qpy+xy=qpy+kp+1=(qy+k)p+1。因?yàn)閏=ay,所以c=1。因?yàn)閎是c在R中的逆元,所以有cb≡1(modn),因?yàn)閏=ay,所以ayb≡1(modn),因此a在R中的逆元是yb。根據(jù)定理2,在計(jì)算R中的逆元的算法中,可以假設(shè)a的p進(jìn)制數(shù)的0位數(shù)是1。1.2計(jì)算逆元的歸納法設(shè)小于n=pk的正整數(shù)a的p進(jìn)制數(shù)表示為a[0:k-1],其中a[i]是a的p進(jìn)制數(shù)第i位數(shù)。以下對(duì)于R的可逆元a給出階的定義。定義設(shè)a=1。(1)若a≠0,令a的階為1;(2)若a=0,…,a[s-1]=0,a[s]≠0(1<s<k),令a的階為s;(3)若a=0,…,a[k-1]=0,令a的階為k。顯然a的階為k當(dāng)且僅當(dāng)a=1。定理3設(shè)a=1,a的階為s(s<k)。若a[s]=h,令c=2sh,b=a-ca,則b的p進(jìn)制數(shù)的0位數(shù)b=1,b的階大于s。證明:因?yàn)閏=2sh(h≠0),顯然c=…=c[s-1]=0,c[s]=h。又因?yàn)閍的階是s,所以a=1,a=…=a[s-1]=0,a[s]=h。因?yàn)閎=a-ca,所以b=1,…,b[s-1]=0,b[s]=a[s]-c[s]=0。根據(jù)階的定義,b的階大于s。定理4設(shè)a是R的元素,a=1。則存在R的元素c使得a-ca的階是k。證明:用數(shù)學(xué)歸納法。若a=1,令c=0即得。設(shè)對(duì)于階大于s的數(shù)a(a=1)定理的結(jié)論成立。若a的階為s,a[s]=h(h≠0),根據(jù)定理3,存在c=2sh,使得b=a-ca的階大于s。且b=1。由歸納法假設(shè),對(duì)于b存在d,使得b-db的階是k。因此a-ca-d(a-ca)=b-db的階是k,即a-(c+d+dc)a的階是k。推論:設(shè)a、c如定理4所述,則(1-c)%n是a在R中的逆元。證明:因?yàn)閍-ca的階是k,所以a(1-c)≡1(modn)。設(shè)x=(1-c)%n,則0<x<n。因此x是R中的元素且x是a的逆元。上述結(jié)論提供了計(jì)算逆元的逐位消除法的理論根據(jù)。逐位消除法是迭代算法。對(duì)于R的可逆元a,首先計(jì)算a的p進(jìn)數(shù)的各個(gè)位的數(shù)字a[i]。如果a=0則a不可逆,若a≠1,計(jì)算a在Z(p)中的逆元y,用ay代替a,可使a=1。設(shè)置數(shù)組b[]=a[],正整數(shù)b,初值是1。如果s是b[]中不為0的數(shù)的最小位數(shù),用c=2sh乘以a[]的各位數(shù)作為減數(shù)。將b[]的各位數(shù)減去該減數(shù),就可以使b[]的第s位為0。b[]的第1到s位數(shù)都是0。繼續(xù)上面的做法,直到s=k-1終止。在每次迭代中,b減去c,迭代終止時(shí),作為a的逆元返回b%n。2相應(yīng)b值a:啟示函數(shù)inv(p,k,a)用來(lái)在模n=pk剩余類環(huán)中計(jì)算可逆元的逆元。p是不大的素?cái)?shù),a是小于n的非負(fù)整數(shù)。(1)intinv(intp,intk,inta)(2){(3)intn=pow(p,k);(4)intu=a%p;(5)if(u=0)return(0);(6)elseif(u>1){(7)v=inv1(p,u);(8)a*=v;(9)if(a>=p)a%=n;(10)}(11)for(i=0;i<k;i++)(12){(13)x=a/p;(14)a[i]=a-x*p;(15)b[i]=a[i];(16)a=x;(17)}(18)intb=1,y=1;(19)for(i=1,i<k,i++)(20){(21)y*=p;(22)b-=b[i]*y;(23)for(j=1;j<k,j++){(24)b[j]-=b[i]*a[j-i];(25)if((b[j]<0)&&(b[j]>=p)){(26)w=b[j]/p;(27)b[j]-=w/p;(28)b[j+1]+=w;(29)}(30)}(31)b[i]=0;(32)}(33)b*=v;(34)if((b>0)&&(b>=p))b%=n;(35)return(b);(36)}intinv1(p,u){intx=p,y=u,c=0,