蒙哥马利模乘(Montgomery Modular Multiplication)学习
蒙哥马利模乘：
设a=3，b=5，N=7，R=10，求：a*b(mod N)
解：
a*b(mod N) = (a*b*R(mod N))/R=( a*b*R + mN )( mod N)/R
m = a*b*(-N-1)(mod R)
-N-1 = -( N-1)
根据欧拉公式：
NΦ(m) mod(m) = 1;
NΦ(m) -1mod(m) = 1;
有：
7Φ(10) -1 mod(10) = 7-1
Φ(10): 10 = 2 * 5
Φ(10) = ( 21 – 20 )*( 51 – 50) = 4 ;
因此：
N-1 mod(10)= 7-1 mod(10) = 7Φ(10)-1 mod(10) = 7 4 - 1 mod(10)
=73 mod(10) = 3
在R为10 的有限域内，N-1 则- N-1 = 7；
m = a*b*(-N-1)(mod R)
= 3*5*7 mod(10)
= 5
令
T= a*b*R(mod N) = 15*（10 mod 7）= 45
则有：
a*b(mod N) = ( a*b*R + mN )( mod N)/R
=（T + mN）/R
= (45+ 5*7)/ 10= 8
