# 模幂

（重定向自模幂运算

c = be mod m = de mod m，其中 e < 0bd ≡ 1 (mod m)

## 直接算法

c ≡ 413 (mod 497)

## 内存优化

c mod m = (ab) mod m
c mod m = [(a mod m) ⋅ (b mod m)] mod m

1. c = 1e′ = 0
2. e′自增1。
3. c = (b ⋅ c) mod m.
4. e′ < e，则返回第二步；否则，c即为cbe (mod m)

• e′ = 1. c = (1 ⋅ 4) mod 497 = 4 mod 497 = 4.
• e′ = 2. c = (4 ⋅ 4) mod 497 = 16 mod 497 = 16.
• e′ = 3. c = (16 ⋅ 4) mod 497 = 64 mod 497 = 64.
• e′ = 4. c = (64 ⋅ 4) mod 497 = 256 mod 497 = 256.
• e′ = 5. c = (256 ⋅ 4) mod 497 = 1024 mod 497 = 30.
• e′ = 6. c = (30 ⋅ 4) mod 497 = 120 mod 497 = 120.
• e′ = 7. c = (120 ⋅ 4) mod 497 = 480 mod 497 = 480.
• e′ = 8. c = (480 ⋅ 4) mod 497 = 1920 mod 497 = 429.
• e′ = 9. c = (429 ⋅ 4) mod 497 = 1716 mod 497 = 225.
• e′ = 10. c = (225 ⋅ 4) mod 497 = 900 mod 497 = 403.
• e′ = 11. c = (403 ⋅ 4) mod 497 = 1612 mod 497 = 121.
• e′ = 12. c = (121 ⋅ 4) mod 497 = 484 mod 497 = 484.
• e′ = 13. c = (484 ⋅ 4) mod 497 = 1936 mod 497 = 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}}$

be的值可写作：

${\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


## 软件实现

• Python内置的pow()（求幂）函数[1]
• .NET框架BigInteger类的ModPow()方法
• Javajava.math.BigInteger类的modPow()方法
• PerlMath::BigInt模块的bmodpow()方法[2]
• Raku内置的expmod例程
• Gobig.Int类的Exp()（求幂）方法[3]
• PHP的BC Math库的bcpowmod()函数[4]
• GNU多重精度运算库（GMP）的mpz_powm()函数[5]
• FileMaker Pro的@PowerMod()函数（以1024位RSA加密为例）
• Rubyopenssl包的OpenSSL::BN#mod_exp方法[6]
• HP Prime计算器的CAS.powmod()函数[7]

## 参考资料

1. ^ Weak Diffie-Hellman and the Logjam Attack. weakdh.org. [2019-05-03].
2. ^ Schneier 1996, p. 244.