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