模重复平方计算法

$b^n\left(\mod m\right)$

• STEP1: 将$n$写成二进制

  $n=n_0+n_1 2+\cdots+n_{k-1}2^{k-1}$

• STEP2: 计算

  $a=1$

  $a_{k-1}$即为$b^n\left(\mod m\right)$