跳至內容

模冪

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

模冪(英語:modular exponentiation)是一種對進行的運算,在電腦科學,尤其是公開金鑰加密方面有一定用途。

模冪運算是指求整數次方正整數所除得到的餘數的過程,可用數學符號表示為。由的定義可得

例如,給定被13除得的餘數

指數為負數時可使用擴充歐幾里得演算法找到模除模反元素來執行模冪運算,即:

,其中

即使在整數很大的情況下,上述模冪運算其實也是易於執行的。然而,計算模的離散對數(即在已知時求出指數)則較為困難。這種類似單向函數的表現使模冪運算可用於加密演算法。

直接演算法

計算模冪的最直接方法是直接算出,再把結果模除。假設已知,以及,要求

可用計數機算得413結果為67,108,864,模除497,可得c等於445。

注意到只有一位,也只有兩位,但的值卻有8位元。

強加密時通常至少有1024位元[1]。考慮的情況,的長度為77位,的長度為2位,但是的值以十進制表示卻已經有1304位元。現代電腦雖然可以進行這種計算,但計算速度卻大大降低。

用這種演算法求模冪所需的時間取決於操作環境和處理器,時間複雜度為

空間最佳化

這種方法比第一種所需要的步驟更多,但所需主記憶體空間和時間均大為減少,其原理為: 給定兩個整數,以下兩個等式是等價的[錨點失效]

演算法如下:

  1. 自增1。
  2. .
  3. ,則返回第二步;否則,即為

再以為例說明,演算法第三步需要執行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]。其中baseexponentmodulus分別對應上式中的

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步。

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

軟件實現

鑑於模冪運算是電腦科學中的重要操作,並且已有高效演算法,所以許多程式語言和高精度整數庫都有執行模冪運算的函數:

另見

參考資料

  1. ^ Weak Diffie-Hellman and the Logjam Attack. weakdh.org. [2019-05-03]. (原始內容存檔於2021-03-29). 
  2. ^ Schneier 1996, p. 244.

外部連結