# 模幂

${\displaystyle c=b^{e}{\bmod {m}}=d^{-e}{\bmod {m}}}$，其中 ${\displaystyle e<0}$${\displaystyle b\cdot d\equiv 1{\pmod {m}}}$

## 直接算法

${\displaystyle c\equiv 4^{13}{\pmod {497}}}$

## 内存优化

${\displaystyle c{\bmod {m}}=(a\cdot b){\bmod {m}}}$
${\displaystyle c{\bmod {m}}=[(a{\bmod {m}})\cdot (b{\bmod {m}})]{\bmod {m}}}$

1. ${\displaystyle c=1}$${\displaystyle e'=0}$
2. ${\displaystyle e'}$自增1。
3. ${\displaystyle c=(b\cdot c){\bmod {m}}}$.
4. ${\displaystyle e'，则返回第二步；否则，${\displaystyle c}$即为${\displaystyle c\equiv b^{e}{\pmod {m}}}$

• ${\displaystyle e'=1\cdot c=(1\cdot 4){\bmod {4}}97=4{\bmod {4}}97=4}$
• ${\displaystyle e'=2\cdot c=(4\cdot 4){\bmod {4}}97=16{\bmod {4}}97=16}$
• ${\displaystyle e'=3\cdot c=(16\cdot 4){\bmod {4}}97=64{\bmod {4}}97=64}$
• ${\displaystyle e'=4\cdot c=(64\cdot 4){\bmod {4}}97=256{\bmod {4}}97=256}$
• ${\displaystyle e'=5\cdot c=(256\cdot 4){\bmod {4}}97=1024{\bmod {4}}97=30}$
• ${\displaystyle e'=6\cdot c=(30\cdot 4){\bmod {4}}97=120{\bmod {4}}97=120}$
• ${\displaystyle e'=7\cdot c=(120\cdot 4){\bmod {4}}97=480{\bmod {4}}97=480}$
• ${\displaystyle e'=8\cdot c=(480\cdot 4){\bmod {4}}97=1920{\bmod {4}}97=429}$
• ${\displaystyle e'=9\cdot c=(429\cdot 4){\bmod {4}}97=1716{\bmod {4}}97=225}$
• ${\displaystyle e'=10\cdot c=(225\cdot 4){\bmod {4}}97=900{\bmod {4}}97=403}$
• ${\displaystyle e'=11\cdot c=(403\cdot 4){\bmod {4}}97=1612{\bmod {4}}97=121}$
• ${\displaystyle e'=12\cdot c=(121\cdot 4){\bmod {4}}97=484{\bmod {4}}97=484}$
• ${\displaystyle e'=13\cdot c=(484\cdot 4){\bmod {4}}97=1936{\bmod {4}}97=445}$

function modular_pow(b, e, m)
if m = 1
then return 0
c := 1
for e' = 0 to e-1
c := (c * b) mod m
return c


## 从右到左二位算法

${\displaystyle e=\sum _{i=0}^{n-1}a_{i}2^{i}}$

${\displaystyle b^{e}}$的值可写作：

${\displaystyle b^{e}=b^{\left(\sum _{i=0}^{n-1}a_{i}2^{i}\right)}=\prod _{i=0}^{n-1}\left(b^{2^{i}}\right)^{a_{i}}}$

${\displaystyle c\equiv \prod _{i=0}^{n-1}\left(b^{2^{i}}\right)^{a_{i}}\ ({\mbox{mod}}\ m)}$

### 伪代码

function modular_pow(base, exponent, modulus)
if modulus = 1 then return 0
Assert :: (modulus - 1) * (modulus - 1) does not overflow base
result := 1
base := base mod modulus
while exponent > 0
if (exponent mod 2 == 1):
result := (result * base) mod modulus
exponent := exponent >> 1
base := (base * base) mod modulus
return result


${\displaystyle R\leftarrow 1\,(=b^{0}){\text{且 }}x\leftarrow b}$.

${\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{2})}$

${\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{4})}$

${\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{8})}$

${\displaystyle R\leftarrow 1\,(=b^{0})}$${\displaystyle x\leftarrow b=4}$

${\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{2})\equiv 4^{2}\equiv 16{\pmod {497}}}$

${\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{4})\equiv 16^{2}{\pmod {497}}\equiv 256{\pmod {497}}}$

${\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{8})\equiv 256^{2}{\pmod {497}}\equiv 429{\pmod {497}}}$

### Lua实现

function modPow(b,e,m)
if m == 1 then
return 0
else
local r = 1
b = b % m
while e > 0 do
if e % 2 == 1 then
r = (r*b) % m
end
e = e >> 1     --Lua 5.2或更早版本使用e = math.floor(e / 2)
b = (b^2) % m
end
return r
end
end


## 参考资料

1. ^ Weak Diffie-Hellman and the Logjam Attack. weakdh.org. [2019-05-03]. （原始内容存档于2021-03-29）.
2. ^ Schneier 1996, p. 244.