Loading AI tools
来自维基百科,自由的百科全书
模冪(英語:modular exponentiation)是一種對模進行的冪運算,在電腦科學,尤其是公開金鑰加密方面有一定用途。
模冪運算是指求整數的次方被正整數所除得到的餘數的過程,可用數學符號表示為。由的定義可得。
例如,給定,和,被13除得的餘數。
指數為負數時可使用擴充歐幾里得演算法找到模除的模反元素來執行模冪運算,即:
即使在整數很大的情況下,上述模冪運算其實也是易於執行的。然而,計算模的離散對數(即在已知,和時求出指數)則較為困難。這種類似單向函式的表現使模冪運算可用於加密演算法。
計算模冪的最直接方法是直接算出,再把結果模除。假設已知,,以及,要求:
可用計算機算得413結果為67,108,864,模除497,可得c等於445。
注意到只有一位,也只有兩位,但的值卻有8位元。
強加密時通常至少有1024位元[1]。考慮和的情況,的長度為77位,的長度為2位,但是的值以十進制表示卻已經有1304位元。現代電腦雖然可以進行這種計算,但計算速度卻大大降低。
用這種演算法求模冪所需的時間取決於操作環境和處理器,時間複雜度為。
這種方法比第一種所需要的步驟更多,但所需主記憶體空間和時間均大為減少,其原理為: 給定兩個整數和,以下兩個等式是等價的:
演算法如下:
再以,,為例說明,演算法第三步需要執行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的值儲存在變數中:
綜上,為。
以下計算的次方對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
鑑於模冪運算是電腦科學中的重要操作,並且已有高效演算法,所以許多程式語言和高精度整數庫都有執行模冪運算的函式:
pow()
(求冪)函式[1] (頁面存檔備份,存於網際網路檔案館)BigInteger
類的ModPow()
方法java.math.BigInteger
類的modPow()
方法Math::BigInt
模組的bmodpow()
方法[2] (頁面存檔備份,存於網際網路檔案館)expmod
常式big.Int
類的Exp()
(求冪)方法[3] (頁面存檔備份,存於網際網路檔案館)bcpowmod()
函式[4] (頁面存檔備份,存於網際網路檔案館)mpz_powm()
函式[5] (頁面存檔備份,存於網際網路檔案館)@PowerMod()
函式(以1024位元RSA加密為例)openssl
包的OpenSSL::BN#mod_exp
方法[6] (頁面存檔備份,存於網際網路檔案館)Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.