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

  1<i *i="" +m="" +…+m="" 0="" 1="" 2="" 2*m="" <i="" i="" k="" m="" 模数="" ；="">I  ； 
  2
  3求解：  A % M 
  4
  5解法： 
  6
  7设：  N=I  k+1  -M  ； 
  8
  9因为：  m  k  &gt;0  ； 
 10
 11所以设：  N=n  0  *I  0  +n  1  *I  1  +n  2  *I  2  +…+n  k  *I  k  ；  n  i  <i a%m="A" e="" e<k="" 当="" 时：="" ；="">k  时： 
 12
 13设：  z=e-k-1  ； 
 14
 15因为：  I&gt;=m  k  +1  ； 
 16
 17所以： 
 18
 19a  e  *I*I  e-1  &gt;= m  k  *a  e  *I  e-1  +a  e  *I  e-1  ； 
 20
 21a  e  *I  e  &gt;=a  e  *m  k  *I  k+z  +a  e  *I  k+z  ； 
 22
 23a  e  *I  e  &gt;=a  e  *I  z  *(m  k  *I  k  +I  k  )  ； 
 24
 25因为： 
 26
 27I  k  &gt;m  0  +m  1  *I  1  +m  2  *I  2  +…+m  k-1  *I  k-1  ； 
 28
 29I  k  +m  k  *I  k  &gt;M  ； 
 30
 31A&gt;=a  e  *I  e  ； 
 32
 33所以： 
 34
 35A&gt;a  e  *I  z  *M  ； 
 36
 37A%M=(A-a  e  *I  z  *M)%M  ； 
 38
 39A%M=(A-a  e  *I  z  *(I  k+1  -N))%M  ； 
 40
 41A%M=(A-a  e  *I  z  *I  k+1  +a  e  *I  z  *N)%M  ； 
 42
 43A%M=((a  0  +a  1  *I  1  +…+a  e-1  *I  e-1  )+a  e  *I  z  *N)%M  ； 
 44
 45A%M=((a  0  +a  1  *I  1  +…+a  z-1  *I  z-1  )+(a  z  *I  z  +a  z+1  *I  z+1  +…+a  e-1  *I  e-1  )+a  e  *I  z  *N)%M  ； 
 46
 47A%M=((a  0  +a  1  *I  1  +…+a  z-1  *I  z-1  ) 
 48
 49+((a  z  *I  z  +a  z+1  *I  z+1  +…+a  e-1  *I  e-1  )+a  e  *I  z  *( n  0  +n  1  *I  1  +…+n  k  *I  k  )))%M  ； 
 50
 51A%M=((a  0  +a  1  *I  1  +…+a  z-1  *I  z-1  ) 
 52
 53+((a  z  *I  z  +a  z+1  *I  z+1  +…+a  e-1  *I  e-1  )+a  e  *( n  0  *I  z  +n  1  *I  z+1  +…+n  k  *I  e-1  )))%M  ； 
 54
 55A%M=((a  0  +a  1  *I  1  +…+a  z-1  *I  z-1  ) 
 56
 57+((a  z  +a  e  *n  0  )*I  z  +(a  z+1  +a  e  *n  1  )*I  z+1  +…+(a  e-1  +a  e  *n  k  )*I  e-1  ))%M  ； 
 58
 59当  e=k  时： 
 60
 61当  A<m a="" a%m="A" 当="" 时：="" ；="">=M  时： 
 62
 63因为：  2*m  k  &gt;I  ； 
 64
 65所以： 
 66
 672*M&gt;A  ； 
 68
 69M&gt;A-M&gt;=0  ； 
 70
 71A%M=A-M=A+N-I  k+1  = (A+N)%I  k+1  ； 
 72
 73C  #  代码实现： 
 74
 75摘自笔者的  Cms.Security.Rsa  类，详细代码请  Email  ：  [email protected]  或  QQ  ：  228512046  向笔者索要。 
 76
 77///  <summary>
 78
 79///  计算无符号大整数模无符号大整数的余数。 
 80
 81///  </summary>
 82
 83///  <param name="InX"/> 被余数，调用后值会改变  
 84
 85///  <param name="ADCM"/> 模数的补数，ADCM[Length-1]的值越小计算越快  
 86
 87///  <param name="OutV"/> 存储余数值用，数组长度应等于或大于模数数组长度  
 88
 89private  void  mod(  uint  [] InX,  uint  [] ADCM,  uint  [] OutV) 
 90
 91{ 
 92
 93/* 
 94
 95* 如果你的调用程序不能确定OutV数组长度是否等于模数数组长度，请启用此条语句。 
 96
 97*注意OutV数组长度不能小于模数数组长度。 
 98
 99*Array.Clear(OutV,0,OutV.Length); 
100
101*/ 
102
103int  i,iv; 
104
105uint  Mult; 
106
107ulong  Temp; 
108
109int  Len_X=InX.Length; 
110
111int  Len_M=ADCM.Length; 
112
113if  (Len_X<len_m) (--len_x="" (i="Len_X;i&lt;Len_M;i++)" ;="" array.copy(inx,0,outv,0,len_x);="" for="" outv[i]="0;" return="" while="" {="" }="">=Len_M) 
114
115{ 
116
117Mult=InX[Len_X]; 
118
119InX[Len_X]=0; 
120
121while  (Mult&gt;0) 
122
123{ 
124
125Temp=0; 
126
127iv=Len_X-Len_M; 
128
129for  (i=0;i<len_m;i++) )adcm[i]="" )temp;="" *="" +="" inx[iv]="(" inx[iv];="" mult="" temp="" temp+="(" uint="" ulong="" {="">&gt;=32; 
130
131iv++; 
132
133} 
134
135Mult=(  uint  )Temp; 
136
137} 
138
139} 
140
141Temp=0; 
142
143for  (i=0;i<len_m;i++) )adcm[i]="" )temp;="" +="" inx[i];="" outv[i]="(" temp="" temp+="(" uint="" ulong="" {="">&gt;=32; 
144
145} 
146
147if  (Temp!=1) Array.Copy(InX,0,OutV,0,Len_M); 
148
149}</len_m;i++)></len_m;i++)></len_m)></m></i></i>