快速求m^e mod n算法

时间:2024-04-11 14:56:20
在非对称密码*(公钥密码*)中常常涉及指数模运算,如计算73327 mod 37 
一种方法是利用前面介绍的模运算性质(a×b) mod m = ((a mod m) × (b mod m)) mod m,将指数模运算可以看做是多次重复乘法,并且在计算中间结果时就取模。
例如:计算117mod 13,可以按照下面的思路:
   112=121≡4 mod 13
   114= (112)2≡42mod 13 ≡3 mod 13

   117=11×112×114≡ 11×4×3 mod 13 ≡ 132 mod 13 ≡2 mod 13

快速求m^e mod n算法一 :

(<-指的是赋值的意思)

快速求m^e mod n算法

例子:

计算30^37 mod 77 

快速求m^e mod n算法

计算3^103(mod 143)=?

快速求m^e mod n算法
最后的结果为16.也就是C的值。