模幂 (英语:modular exponentiation )是一种对模 进行的幂 运算,在计算机科学 ,尤其是公开密钥加密 方面有一定用途。
模幂运算是指求整数
b
{\displaystyle b}
的
e
{\displaystyle e}
次方
b
e
{\displaystyle b^{e}}
被正整数
m
{\displaystyle m}
所除得到的余数
c
{\displaystyle c}
的过程,可用数学符号表示为
c
=
b
e
mod
m
{\displaystyle c=b^{e}{\bmod {m}}}
。由
c
{\displaystyle c}
的定义可得
0
≤
c
<
m
{\displaystyle 0\leq c<m}
。
例如,给定
b
=
5
{\displaystyle b=5}
,
e
=
3
{\displaystyle e=3}
和
m
=
13
{\displaystyle m=13}
,
5
3
=
125
{\displaystyle 5^{3}=125}
被13除得的余数
c
=
8
{\displaystyle c=8}
。
指数
e
{\displaystyle e}
为负数时可使用扩展欧几里得算法 找到
b
{\displaystyle b}
模除
m
{\displaystyle m}
的模逆元
d
{\displaystyle d}
来执行模幂运算,即:
c
=
b
e
mod
m
=
d
−
e
mod
m
{\displaystyle c=b^{e}{\bmod {m}}=d^{-e}{\bmod {m}}}
,其中
e
<
0
{\displaystyle e<0}
且
b
⋅
d
≡
1
(
mod
m
)
{\displaystyle b\cdot d\equiv 1{\pmod {m}}}
。
即使在整数很大的情况下,上述模幂运算其实也是易于执行的。然而,计算模的离散对数 (即在已知
b
{\displaystyle b}
,
c
{\displaystyle c}
和
m
{\displaystyle m}
时求出指数
e
{\displaystyle e}
)则较为困难。这种类似单向函数 的表现使模幂运算可用于加密算法。
直接算法
计算模幂的最直接方法是直接算出
b
e
{\displaystyle b^{e}}
,再把结果模除
m
{\displaystyle m}
。假设已知
b
=
4
{\displaystyle b=4}
,
e
=
13
{\displaystyle e=13}
,以及
m
=
497
{\displaystyle m=497}
,要求
c
{\displaystyle c}
:
c
≡
4
13
(
mod
497
)
{\displaystyle c\equiv 4^{13}{\pmod {497}}}
可用计算器算得413 结果为67,108,864,模除497,可得c 等于445。
注意到
b
{\displaystyle b}
只有一位,
e
{\displaystyle e}
也只有两位,但
b
e
{\displaystyle b^{e}}
的值却有8位。
强加密时
b
{\displaystyle b}
通常至少有1024位[ 1] 。考虑
b
=
5
×
10
76
{\displaystyle b=5\times 10^{76}}
和
e
=
17
{\displaystyle e=17}
的情况,
b
{\displaystyle b}
的长度为77位,
e
{\displaystyle e}
的长度为2位,但是
b
e
{\displaystyle b^{e}}
的值以十进制 表示却已经有1304位。现代计算机虽然可以进行这种计算,但计算速度却大大降低。
用这种算法求模幂所需的时间取决于操作环境和处理器,时间复杂度为
O
(
e
)
{\displaystyle \mathrm {O} (e)}
。
空间优化
这种方法比第一种所需要的步骤更多,但所需内存空间和时间均大为减少,其原理为:
给定两个整数
a
{\displaystyle a}
和
b
{\displaystyle b}
,以下两个等式是等价的 :
c
mod
m
=
(
a
⋅
b
)
mod
m
{\displaystyle c{\bmod {m}}=(a\cdot b){\bmod {m}}}
c
mod
m
=
[
(
a
mod
m
)
⋅
(
b
mod
m
)
]
mod
m
{\displaystyle c{\bmod {m}}=[(a{\bmod {m}})\cdot (b{\bmod {m}})]{\bmod {m}}}
算法如下:
令
c
=
1
{\displaystyle c=1}
,
e
′
=
0
{\displaystyle e'=0}
。
e
′
{\displaystyle e'}
自增1。
令
c
=
(
b
⋅
c
)
mod
m
{\displaystyle c=(b\cdot c){\bmod {m}}}
.
若
e
′
<
e
{\displaystyle e'<e}
,则返回第二步;否则,
c
{\displaystyle c}
即为
c
≡
b
e
(
mod
m
)
{\displaystyle c\equiv b^{e}{\pmod {m}}}
。
再以
b
=
4
{\displaystyle b=4}
,
e
=
13
{\displaystyle e=13}
,
m
=
497
{\displaystyle m=497}
为例说明,算法第三步需要执行13次:
e
′
=
1
⋅
c
=
(
1
⋅
4
)
mod
4
97
=
4
mod
4
97
=
4
{\displaystyle e'=1\cdot c=(1\cdot 4){\bmod {4}}97=4{\bmod {4}}97=4}
e
′
=
2
⋅
c
=
(
4
⋅
4
)
mod
4
97
=
16
mod
4
97
=
16
{\displaystyle e'=2\cdot c=(4\cdot 4){\bmod {4}}97=16{\bmod {4}}97=16}
e
′
=
3
⋅
c
=
(
16
⋅
4
)
mod
4
97
=
64
mod
4
97
=
64
{\displaystyle e'=3\cdot c=(16\cdot 4){\bmod {4}}97=64{\bmod {4}}97=64}
e
′
=
4
⋅
c
=
(
64
⋅
4
)
mod
4
97
=
256
mod
4
97
=
256
{\displaystyle e'=4\cdot c=(64\cdot 4){\bmod {4}}97=256{\bmod {4}}97=256}
e
′
=
5
⋅
c
=
(
256
⋅
4
)
mod
4
97
=
1024
mod
4
97
=
30
{\displaystyle e'=5\cdot c=(256\cdot 4){\bmod {4}}97=1024{\bmod {4}}97=30}
e
′
=
6
⋅
c
=
(
30
⋅
4
)
mod
4
97
=
120
mod
4
97
=
120
{\displaystyle e'=6\cdot c=(30\cdot 4){\bmod {4}}97=120{\bmod {4}}97=120}
e
′
=
7
⋅
c
=
(
120
⋅
4
)
mod
4
97
=
480
mod
4
97
=
480
{\displaystyle e'=7\cdot c=(120\cdot 4){\bmod {4}}97=480{\bmod {4}}97=480}
e
′
=
8
⋅
c
=
(
480
⋅
4
)
mod
4
97
=
1920
mod
4
97
=
429
{\displaystyle e'=8\cdot c=(480\cdot 4){\bmod {4}}97=1920{\bmod {4}}97=429}
e
′
=
9
⋅
c
=
(
429
⋅
4
)
mod
4
97
=
1716
mod
4
97
=
225
{\displaystyle e'=9\cdot c=(429\cdot 4){\bmod {4}}97=1716{\bmod {4}}97=225}
e
′
=
10
⋅
c
=
(
225
⋅
4
)
mod
4
97
=
900
mod
4
97
=
403
{\displaystyle e'=10\cdot c=(225\cdot 4){\bmod {4}}97=900{\bmod {4}}97=403}
e
′
=
11
⋅
c
=
(
403
⋅
4
)
mod
4
97
=
1612
mod
4
97
=
121
{\displaystyle e'=11\cdot c=(403\cdot 4){\bmod {4}}97=1612{\bmod {4}}97=121}
e
′
=
12
⋅
c
=
(
121
⋅
4
)
mod
4
97
=
484
mod
4
97
=
484
{\displaystyle e'=12\cdot c=(121\cdot 4){\bmod {4}}97=484{\bmod {4}}97=484}
e
′
=
13
⋅
c
=
(
484
⋅
4
)
mod
4
97
=
1936
mod
4
97
=
445
{\displaystyle e'=13\cdot c=(484\cdot 4){\bmod {4}}97=1936{\bmod {4}}97=445}
因此最终结果
c
{\displaystyle c}
为445,与第一种方法所求结果相等。
与第一种方法相同,这种算法需要
O
(
e
)
{\displaystyle \mathrm {O} (e)}
的时间才能完成。但是,由于在计算过程中处理的数字比第一种算法小得多,因此计算时间至少减少了
O
(
e
)
{\displaystyle \mathrm {O} (e)}
倍。
算法伪代码如下:
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
从右到左二位算法
第三种方法结合了第二种算法和平方求幂 原理,使所需步骤大大减少,同时也与第二种方法一样减少了内存占用量。
首先把
e
{\displaystyle e}
表示成二进制 ,即:
e
=
∑
i
=
0
n
−
1
a
i
2
i
{\displaystyle e=\sum _{i=0}^{n-1}a_{i}2^{i}}
此时
e
{\displaystyle e}
的长度为
n
{\displaystyle n}
位。对任意
i
{\displaystyle i}
(
0
≤
i
<
n
{\displaystyle 0\leq i<n}
),
a
i
{\displaystyle a_{i}}
可取0或1任一值。由定义有
a
n
−
1
=
1
{\displaystyle a_{n-1}=1}
。
b
e
{\displaystyle b^{e}}
的值可写作:
b
e
=
b
(
∑
i
=
0
n
−
1
a
i
2
i
)
=
∏
i
=
0
n
−
1
(
b
2
i
)
a
i
{\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}}}
因此答案
c
{\displaystyle c}
即为:
c
≡
∏
i
=
0
n
−
1
(
b
2
i
)
a
i
(
mod
m
)
{\displaystyle c\equiv \prod _{i=0}^{n-1}\left(b^{2^{i}}\right)^{a_{i}}\ ({\mbox{mod}}\ m)}
伪代码
下述伪代码基于布鲁斯·施奈尔 所著《应用密码学》[ 2] 。其中base ,exponent 和modulus 分别对应上式中的
b
{\displaystyle b}
,
e
{\displaystyle e}
和
m
{\displaystyle 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
注意到在首次进入循环时,变量base 等于
b
{\displaystyle b}
。在第三行代码中重复执行平方运算,会确保在每次循环结束时,变量base 等于
b
2
i
mod
m
{\displaystyle b^{2^{i}}{\bmod {m}}}
,其中
i
{\displaystyle i}
是循环执行次数。
本例中,底数
b
{\displaystyle b}
的指数为
e
=
13
{\displaystyle e=13}
。
指数用二进制表示为1101,有4位,故循环执行4次。
4位数字从右到左依次为1,0,1,1。
首先,初始化结果
R
{\displaystyle R}
为1,并将b 的值保存在变量
x
{\displaystyle x}
中:
R
←
1
(
=
b
0
)
且
x
←
b
{\displaystyle R\leftarrow 1\,(=b^{0}){\text{且 }}x\leftarrow b}
.
第1步 第1位为1,故令
R
←
R
⋅
x
(
=
b
1
)
{\displaystyle R\leftarrow R\cdot x{\text{ }}(=b^{1})}
;
令
x
←
x
2
(
=
b
2
)
{\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{2})}
。
第2步 第2位为0,故不给R 赋值;
令
x
←
x
2
(
=
b
4
)
{\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{4})}
。
第3步 第3位为1,故令
R
←
R
⋅
x
(
=
b
5
)
{\displaystyle R\leftarrow R\cdot x{\text{ }}(=b^{5})}
;
令
x
←
x
2
(
=
b
8
)
{\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{8})}
。
第4步 第4位为1,故令
R
←
R
⋅
x
(
=
b
13
)
{\displaystyle R\leftarrow R\cdot x{\text{ }}(=b^{13})}
;
这是最后一步,所以不需要对x 求平方。
综上,
R
{\displaystyle R}
为
b
13
{\displaystyle b^{13}}
。
以下计算
b
=
4
{\displaystyle b=4}
的
e
=
13
{\displaystyle e=13}
次方对497求模的结果。
初始化:
R
←
1
(
=
b
0
)
{\displaystyle R\leftarrow 1\,(=b^{0})}
且
x
←
b
=
4
{\displaystyle x\leftarrow b=4}
。
第1步 第1位为1,故令
R
←
R
⋅
4
(
mod
497
)
≡
4
(
mod
497
)
{\displaystyle R\leftarrow R\cdot 4{\pmod {497}}\equiv 4{\pmod {497}}}
;
令
x
←
x
2
(
=
b
2
)
≡
4
2
≡
16
(
mod
497
)
{\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{2})\equiv 4^{2}\equiv 16{\pmod {497}}}
。
第2步 第2位为0,故不给R 赋值;
令
x
←
x
2
(
=
b
4
)
≡
16
2
(
mod
497
)
≡
256
(
mod
497
)
{\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{4})\equiv 16^{2}{\pmod {497}}\equiv 256{\pmod {497}}}
。
第3步 第3位为1,故令
R
←
R
⋅
x
(
=
b
5
)
≡
4
⋅
256
(
mod
497
)
≡
30
(
mod
497
)
{\displaystyle R\leftarrow R\cdot x{\text{ }}(=b^{5})\equiv 4\cdot 256{\pmod {497}}\equiv 30{\pmod {497}}}
;
令
x
←
x
2
(
=
b
8
)
≡
256
2
(
mod
497
)
≡
429
(
mod
497
)
{\displaystyle x\leftarrow x^{2}{\text{ }}(=b^{8})\equiv 256^{2}{\pmod {497}}\equiv 429{\pmod {497}}}
。
第4步 第4位为1,故令
R
←
R
⋅
x
(
=
b
13
)
≡
30
⋅
429
(
mod
497
)
≡
445
(
mod
497
)
{\displaystyle R\leftarrow R\cdot x{\text{ }}(=b^{13})\equiv 30\cdot 429{\pmod {497}}\equiv 445{\pmod {497}}}
;
综上,
R
{\displaystyle R}
为
4
13
(
mod
497
)
≡
445
(
mod
497
)
{\displaystyle 4^{13}{\pmod {497}}\equiv 445{\pmod {497}}}
,与先前算法中所得结果相同。
该算法时间复杂度为O(log exponent ) 。指数exponent 值较大时,这种算法与前两种O( exponent ) 算法相比具有明显的速度优势。例如,如果指数为220 = 1048576,此算法只需执行20步,而非1,048,576步。
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
软件实现
鉴于模幂运算是计算机科学中的重要操作,并且已有高效算法,所以许多编程语言和高精度整数库都有执行模幂运算的函数:
另见
参考资料
外部链接