模重复平方计算法

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

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

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

• STEP2: 计算

  $a=1$

  \left\{ \begin{array}{**lr**} a_0\equiv a\cdot b^{n_0}\left(\mod m\right), b_1\equiv b^2\left(\mod m\right)\\ a_1\equiv a_0\cdot b_{1}^{n_1}\left(\mod m\right), b_2\equiv b_{1}^{2}\left(\mod m\right)\\ \cdots\\ a_{k-2}\equiv a_{k-3}\cdot b_{k-2}^{n_{k-2}}\left(\mod m\right), b_{k-1}\equiv b_{k-2}^{2}\left(\mod m\right)\\ a_{k-1}\equiv a_{k-2}\cdot b_{k-1}^{n_{k-1}}\left(\mod m\right) \end{array} \right.

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