模n剩余类环中的元素可逆和逆元的计算

模n剩余类环中的元素可逆和逆元的计算

0逆元算法的应用r.z（n）是模式n的剩余环，r的元素a是小于n的非负总数。a在r中的逆反映是指元素b为r敖的元素b。检验R中的元素可逆以及计算可逆元的逆元的算法有广泛的应用(如公钥密码制RSA)。传统的算法是Euclid算法和扩展的Euclid算法,时间复杂度为O(n3)。如果将n限制在比较窄的范围,时间复杂度就要低得多。本文讨论模n=pk剩余类环,其中p是一个不大的素数。在这个环内,任何一个数a(小于pk的非负整数)都可以表示为k位p进制数,因此可以用k维数组a[0:k-1]表示,其中a[i](小于p的非负整数)是a的p进制数的第i位数字。在文中引入a的阶的概念,利用元素的阶,笔者设计计算逆元的逐位消除法,并且对逐位消除法编写程序(C语言)。1该算法1.1被减数不够减时a是r的逆元位置假设p是一个不太大的素数,k是大于1的整数,n=pk,R=Z(n)是模n剩余类环。R的元素是小于n的非负整数。将a的元素对应一个k维数组a[0;k-1],其中a[i](小于p的非负整数)是a的p进制数的第i位数字(从低位到高位)。在R的元素的运算中,因为n≡0(modn),所以在加法和乘法中,超过k位的数应删除;在减法中,被减数不够减时,可以从k位借。定理1设a是R的非0元。a是R的可逆元当且仅当a≠0。证明:在模n剩余类环R中,a可逆当且仅当gcd(c,d)=1。因为n=pk,所以n只有一个素因数p。因此a是可逆元当且仅当p不是a的因数。设a=qp+r(0≤r<p)。因而a是可逆元当且仅当r≠0。由于r=a,因此a是可逆元当且仅当a≠0。定理2设a是R的可逆的元素,a=x。(1)若x在模p剩余类环Z(p)中的逆元是y,即xy≡1(modp),令c=ay,则c的p进制数的0位数c=1。(2)若c在R中的逆元是b,则a在R中的逆元是yb。证明:由于xy≡1(modp),则有整数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。根据定理2,在计算R中的逆元的算法中,可以假设a的p进制数的0位数是1。1.2计算逆元的归纳法设小于n=pk的正整数a的p进制数表示为a[0:k-1],其中a[i]是a的p进制数第i位数。以下对于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进制数的0位数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。根据阶的定义,b的阶大于s。定理4设a是R的元素,a=1。则存在R的元素c使得a-ca的阶是k。证明:用数学归纳法。若a=1,令c=0即得。设对于阶大于s的数a(a=1)定理的结论成立。若a的阶为s,a[s]=h(h≠0),根据定理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的逆元。上述结论提供了计算逆元的逐位消除法的理论根据。逐位消除法是迭代算法。对于R的可逆元a,首先计算a的p进数的各个位的数字a[i]。如果a=0则a不可逆,若a≠1,计算a在Z(p)中的逆元y,用ay代替a,可使a=1。设置数组b[]=a[],正整数b,初值是1。如果s是b[]中不为0的数的最小位数,用c=2sh乘以a[]的各位数作为减数。将b[]的各位数减去该减数,就可以使b[]的第s位为0。b[]的第1到s位数都是0。继续上面的做法,直到s=k-1终止。在每次迭代中,b减去c,迭代终止时,作为a的逆元返回b%n。2相应b值a:启示函数inv(p,k,a)用来在模n=pk剩余类环中计算可逆元的逆元。p是不大的素数,a是小于n的非负整数。(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,