第四章公钥密码:4.1公钥密码常用知识和算法 4.1公钥密码常用知识和算法 蒙哥马利模乘算法计算z= XYR-I mod M 输入:X=(XNm1,,X,F(Y Nw-15··· Yor, M=(M, N-1·· M=(Mo)modr,其中0≤x,Y≤M,2l≤M≤2N,r=",gcd(M,r)=1, NwHN/w Output: Z=XYr- nu mod M 1:Z÷0 2: fori=0 to nu-1 do 3:Z÷z+XY 4:qM÷( Z mod r) M mod r 5:Z÷(2+qMM/r 6: end for 7: ifz>M then 8:Z÷Z-M 9: end if 10: Retun Z 历忠毛孑技*字4.1 公钥密码常用知识和算法  蒙哥马利模乘算法计算Z=XYR-1 mod M  输入：X=(XNw-1 ,…, X0 )r， Y=(YNw-1 ,…, Y0 )r，M=(MNw-1 ,…, M0 )r， M=-(M0 ) -1 mod r ，其中0X, Y M，2 N-1M2 N ， r =2 w ，gcd(M, r)=1， Nw=N/w 7/ 第四章 公钥密码：4.1 公钥密码常用知识和算法