Passion of life
  2. Math

在密码学中重要的是能有效地求, 其中都是大整数。先计算，再求除以的余数是不可行的，因为是非常大的数。可行的是一种利用指数n的二进制展开的算法。这个算法依次求

把其中的那些项相乘，在每次乘法后求乘积除以m的余数。

算法伪代码如下：

1
2
3
4
5
6
7
x = 1
power = b mod(m)
for i = 0 to k-1
begin
if a_i = 1 then x = x * power mod(m)
power = power * power mod(m)
end