一种方法是利用前面介绍的模运算性质(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算法一 :
(<-指的是赋值的意思)
例子:
计算30^37 mod 77
计算3^103(mod 143)=?
最后的结果为16.也就是C的值。