非对称加密算法中求解大正整数模大正整数的余数的快速计算法

类别:.NET开发 点击:0 评论:0 推荐:

前提:

模数的补数小于模数本身;

定义:

假设:I=Uint.MaxValue+1

整数A=a0*I0+a1*I1+a2*I2+…+ae*Ieai<I

模数M=m0*I0+m1*I1+m2*I2+…+mk*Ikmi<I2*mk>I

求解:A % M

解法:

       设:N=Ik+1-M

       因为:mk>0

所以设:N=n0*I0+n1*I1+n2*I2+…+nk*Ikni<I

e<k时:

A%M=A

e>k时:

设:z=e-k-1

       因为:I>=mk+1

       所以:

ae*I*Ie-1>= mk*ae*Ie-1+ae*Ie-1

ae*Ie>=ae*mk*Ik+z+ae*Ik+z

ae*Ie>=ae*Iz *(mk*Ik+Ik)

       因为:

Ik>m0+m1*I1+m2*I2+…+mk-1*Ik-1

              Ik+mk*Ik>M

              A>=ae*Ie

所以:

A>ae*Iz*M

A%M=(A-ae*Iz*M)%M

A%M=(A-ae*Iz*(Ik+1-N))%M

A%M=(A-ae*Iz*Ik+1+ae*Iz*N)%M

A%M=((a0+a1*I1+…+ae-1*Ie-1)+ae*Iz*N)%M

A%M=((a0+a1*I1+…+az-1*Iz-1)+(az*Iz+az+1*Iz+1+…+ae-1*Ie-1)+ae*Iz*N)%M

A%M=((a0+a1*I1+…+az-1*Iz-1)

+((az*Iz+az+1*Iz+1+…+ae-1*Ie-1)+ae*Iz*( n0+n1*I1+…+nk*Ik)))%M

A%M=((a0+a1*I1+…+az-1*Iz-1)

+((az*Iz+az+1*Iz+1+…+ae-1*Ie-1)+ae*( n0*Iz+n1*Iz+1+…+nk*Ie-1)))%M

A%M=((a0+a1*I1+…+az-1*Iz-1)

+((az+ae*n0)*Iz+(az+1+ae*n1)*Iz+1+…+(ae-1+ae*nk)*Ie-1))%M

e=k时:

A<M时:A%M=A

       A>=M时:

因为:2*mk>I

所以:

       2*M>A

       M>A-M>=0

A%M=A-M=A+N-Ik+1= (A+N)%Ik+1

C#代码实现:

摘自笔者的Cms.Security.Rsa类,详细代码请Email[email protected]QQ228512046向笔者索要。

     /// <summary>

     /// 计算无符号大整数模无符号大整数的余数。

     /// </summary>

     /// <param name="InX">被余数,调用后值会改变</param>

     /// <param name="ADCM">模数的补数,ADCM[Length-1]的值越小计算越快</param>

     /// <param name="OutV">存储余数值用,数组长度应等于或大于模数数组长度</param>

     private void mod(uint[] InX,uint[] ADCM,uint[] OutV)

     {

         /*

          * 如果你的调用程序不能确定OutV数组长度是否等于模数数组长度,请启用此条语句。

          *注意OutV数组长度不能小于模数数组长度。

          *Array.Clear(OutV,0,OutV.Length);

         */

         int i,iv;

         uint Mult;

         ulong Temp;

         int Len_X=InX.Length;

         int Len_M=ADCM.Length;

          if(Len_X<Len_M)

         {

              Array.Copy(InX,0,OutV,0,Len_X);

              for(i=Len_X;i<Len_M;i++) OutV[i]=0;

              return;

         }

          while(--Len_X>=Len_M)

         {

              Mult=InX[Len_X];

              InX[Len_X]=0;

              while(Mult>0)

              {

                   Temp=0;

                   iv=Len_X-Len_M;

                   for(i=0;i<Len_M;i++)

                   {

                        Temp+=(ulong)ADCM[i] * Mult + InX[iv];

                        InX[iv]=(uint)Temp;

                        Temp>>=32;

                       iv++;

                   }

                   Mult=(uint)Temp;

              }

         }

          Temp=0;

          for(i=0;i<Len_M;i++)

         {

              Temp+=(ulong)ADCM[i] + InX[i];

              OutV[i]=(uint)Temp;

              Temp>>=32;

         }

          if(Temp!=1) Array.Copy(InX,0,OutV,0,Len_M);

     }

本文地址:http://com.8s8s.com/it/it45567.htm