前提：
模数的补数小于模数本身；
定义：
假设：I=Uint.MaxValue+1；
整数A=a0*I0+a1*I1+a2*I2+…+ae*Ie；ai<I；
模数M=m0*I0+m1*I1+m2*I2+…+mk*Ik；mi<I；2*mk>I；
求解：A % M
解法：
设：N=Ik+1-M；
因为：mk>0；
所以设：N=n0*I0+n1*I1+n2*I2+…+nk*Ik；ni<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]或QQ：228512046向笔者索要。
/// <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