二進制快速取冪法
評估 $ 17^{93} \mod 23 $
$$ \begin{align}e &= 93\ &= 1 × 2^6 + 0 × 2^5 + 1 × 2^4+ 1 × 2^3 + 1 × 2^2 + 0 × 2^1 + 1 × 2^0\ &= |\ 1011101\ |_2 \end{align} $$ 然後我們有： $$ \begin{align}17^{93} \mod 23 &= (((((((17^1 )^2 17^0 )^2 17^1 )^2 17^1 )^2 17^1 )^2 17^0 )^2 17^1\ &= (((17^4 17)^2 17)^2 17)^4 17 \text{ $\leftarrow$ step 3}\ &= 21 \end{align} $$ 我們如何從第 3 步到最終答案？使用的定理是什麼？
這只是一個模乘：
$$ \begin{align}17^{93} \mod 23 &= (((((((17^1 )^2 17^0 )^2 17^1 )^2 17^1 )^2 17^1 )^2 17^0 )^2 17^1\ &= (((((17^2)^2 17)^2 17)^2 17)^2)^2 17 \text{ $\leftarrow$ step 3}\ &= (((((289 \bmod\ 23)^2 17)^2 17)^2 17)^2)^2 17\ &= ((((13^2 17)^2 17)^2 17)^2)^2 17\ &= (((((169 \bmod\ 23) 17)^2 17)^2 17)^2)^2 17\ &= ((((8 \times 17)^2 17)^2 17)^2)^2 17\ &= ((((136 \bmod 23)^2 17)^2 17)^2)^2 17\ &= (((21^2 17)^2 17)^2)^2 17\ &= ((((441\ \bmod\ 23) 17)^2 17)^2)^2 17\ &= (((4 \times 17)^2 17)^2)^2 17\ &= etc..\ &= 21 \end{align} $$