蒙哥马利模乘(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