第四章公钥密码:4.1公钥密码常用知识和算法 4.1公钥密码常用知识和算法 ●四、蒙哥马利算法,避免求模运算中的除法 避免求模过程中复杂耗时的除法( P L. Montgomery,1985年提出) 计算 TR-ImodM (1)=(T+MN/R (2 )IF T2N return T-N; ELSE return T 其中M=( Tmod r)X( N-I mod r)modR,且0<TNR ●而且显然有R(R1modN)+N( v-I mod r)=1+RN (R1mdN以及( N-l modR)可预计算,R常取的幂 般先计算 TR-I mod M,若R=",再不断左移模N共w次可得结 果 历忠毛孑技*字4.1 公钥密码常用知识和算法  四、蒙哥马利算法，避免求模运算中的除法 ⚫ 避免求模过程中复杂耗时的除法（P.L.Montgomery,1985年提出) ⚫ 计算TR-1 mod N ⚫ (1) T=(T+MN)/R ⚫ (2) IF TN return T-N; ELSE return T ⚫ 其中M=(Tmod R)×(N-1 mod R) mod R，且0<T<NR ⚫ 而且显然有R(R-1 mod N)+N(N-1 mod R)=1+RN ⚫ (R-1 mod N)以及(N-1 mod R）可预计算，R常取2的幂 ⚫ 一般先计算TR-1 mod N ，若R=2w，再不断左移模N 共w次可得结 果 6/ 第四章 公钥密码：4.1 公钥密码常用知识和算法