模冪(英語:modular exponentiation)是一種對模進行的冪運算,在計算機科學,尤其是公開密鑰加密方面有一定用途。
模冪運算是指求整數的次方被正整數所除得到的餘數的過程,可用數學符號表示為。由的定義可得。
例如,給定,和,被13除得的餘數。
指數為負數時可使用擴展歐幾里得算法找到模除的模逆元來執行模冪運算,即:
- ,其中 且。
即使在整數很大的情況下,上述模冪運算其實也是易於執行的。然而,計算模的離散對數(即在已知,和時求出指數)則較為困難。這種類似單向函數的表現使模冪運算可用於加密算法。
直接算法
計算模冪的最直接方法是直接算出,再把結果模除。假設已知,,以及,要求:
可用計算器算得413結果為67,108,864,模除497,可得c等於445。
注意到只有一位,也只有兩位,但的值卻有8位。
強加密時通常至少有1024位[1]。考慮和的情況,的長度為77位,的長度為2位,但是的值以十進制表示卻已經有1304位。現代計算機雖然可以進行這種計算,但計算速度卻大大降低。
用這種算法求模冪所需的時間取決於操作環境和處理器,時間複雜度為。
空間優化
這種方法比第一種所需要的步驟更多,但所需內存空間和時間均大為減少,其原理為:
給定兩個整數和,以下兩個等式是等價的:
算法如下:
- 令,。
- 自增1。
- 令.
- 若,則返回第二步;否則,即為。
再以,,為例說明,算法第三步需要執行13次:
因此最終結果為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
從右到左二位算法
第三種方法結合了第二種算法和平方求冪原理,使所需步驟大大減少,同時也與第二種方法一樣減少了內存占用量。
首先把表示成二進制,即:
此時的長度為位。對任意(),可取0或1任一值。由定義有。
的值可寫作:
因此答案即為:
偽代碼
下述偽代碼基於布魯斯·施奈爾所著《應用密碼學》[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
軟件實現
鑑於模冪運算是計算機科學中的重要操作,並且已有高效算法,所以許多編程語言和高精度整數庫都有執行模冪運算的函數:
另見
參考資料
外部連結