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

0逆元算法的應用r.z（n）是模式n的剩余環(huán)，r的元素a是小于n的非負總數(shù)。a在r中的逆反映是指元素b為r敖的元素b。檢驗R中的元素可逆以及計算可逆元的逆元的算法有廣泛的應用(如公鑰密碼制RSA)。傳統(tǒng)的算法是Euclid算法和擴展的Euclid算法,時間復雜度為O(n3)。如果將n限制在比較窄的范圍,時間復雜度就要低得多。本文討論模n=pk剩余類環(huán),其中p是一個不大的素數(shù)。在這個環(huán)內(nèi),任何一個數(shù)a(小于pk的非負整數(shù))都可以表示為k位p進制數(shù),因此可以用k維數(shù)組a[0:k-1]表示,其中a[i](小于p的非負整數(shù))是a的p進制數(shù)的第i位數(shù)字。在文中引入a的階的概念,利用元素的階,筆者設計計算逆元的逐位消除法,并且對逐位消除法編寫程序(C語言)。1該算法1.1被減數(shù)不夠減時a是r的逆元位置假設p是一個不太大的素數(shù),k是大于1的整數(shù),n=pk,R=Z(n)是模n剩余類環(huán)。R的元素是小于n的非負整數(shù)。將a的元素對應一個k維數(shù)組a[0;k-1],其中a[i](小于p的非負整數(shù))是a的p進制數(shù)的第i位數(shù)字(從低位到高位)。在R的元素的運算中,因為n≡0(modn),所以在加法和乘法中,超過k位的數(shù)應刪除;在減法中,被減數(shù)不夠減時,可以從k位借。定理1設a是R的非0元。a是R的可逆元當且僅當a≠0。證明:在模n剩余類環(huán)R中,a可逆當且僅當gcd(c,d)=1。因為n=pk,所以n只有一個素因數(shù)p。因此a是可逆元當且僅當p不是a的因數(shù)。設a=qp+r(0≤r<p)。因而a是可逆元當且僅當r≠0。由于r=a,因此a是可逆元當且僅當a≠0。定理2設a是R的可逆的元素,a=x。(1)若x在模p剩余類環(huán)Z(p)中的逆元是y,即xy≡1(modp),令c=ay,則c的p進制數(shù)的0位數(shù)c=1。(2)若c在R中的逆元是b,則a在R中的逆元是yb。證明:由于xy≡1(modp),則有整數(shù)k使得xy=kp+1。因為a=qp+x,所以ay=qpy+xy=qpy+kp+1=(qy+k)p+1。因為c=ay,所以c=1。因為b是c在R中的逆元,所以有cb≡1(modn),因為c=ay,所以ayb≡1(modn),因此a在R中的逆元是yb。根據(jù)定理2,在計算R中的逆元的算法中,可以假設a的p進制數(shù)的0位數(shù)是1。1.2計算逆元的歸納法設小于n=pk的正整數(shù)a的p進制數(shù)表示為a[0:k-1],其中a[i]是a的p進制數(shù)第i位數(shù)。以下對于R的可逆元a給出階的定義。定義設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當且僅當a=1。定理3設a=1,a的階為s(s<k)。若a[s]=h,令c=2sh,b=a-ca,則b的p進制數(shù)的0位數(shù)b=1,b的階大于s。證明:因為c=2sh(h≠0),顯然c=…=c[s-1]=0,c[s]=h。又因為a的階是s,所以a=1,a=…=a[s-1]=0,a[s]=h。因為b=a-ca,所以b=1,…,b[s-1]=0,b[s]=a[s]-c[s]=0。根據(jù)階的定義,b的階大于s。定理4設a是R的元素,a=1。則存在R的元素c使得a-ca的階是k。證明:用數(shù)學歸納法。若a=1,令c=0即得。設對于階大于s的數(shù)a(a=1)定理的結論成立。若a的階為s,a[s]=h(h≠0),根據(jù)定理3,存在c=2sh,使得b=a-ca的階大于s。且b=1。由歸納法假設,對于b存在d,使得b-db的階是k。因此a-ca-d(a-ca)=b-db的階是k,即a-(c+d+dc)a的階是k。推論:設a、c如定理4所述,則(1-c)%n是a在R中的逆元。證明:因為a-ca的階是k,所以a(1-c)≡1(modn)。設x=(1-c)%n,則0<x<n。因此x是R中的元素且x是a的逆元。上述結論提供了計算逆元的逐位消除法的理論根據(jù)。逐位消除法是迭代算法。對于R的可逆元a,首先計算a的p進數(shù)的各個位的數(shù)字a[i]。如果a=0則a不可逆,若a≠1,計算a在Z(p)中的逆元y,用ay代替a,可使a=1。設置數(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,迭代終止時,作為a的逆元返回b%n。2相應b值a:啟示函數(shù)inv(p,k,a)用來在模n=pk剩余類環(huán)中計算可逆元的逆元。p是不大的素數(shù),a是小于n的非負整數(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,