模幂

维基百科,自由的百科全书
(重定向自模幂运算
跳到导航 跳到搜索

模幂(英語:modular exponentiation)是一种对进行的运算,在计算机科学,尤其是公开密钥加密方面有一定用途。

模幂运算是指求整数be次方be正整数m所除得到的余数c的过程,可用数学符号表示为c = be mod m。由c的定义可得0 ≤ c < m

例如,给定b = 5e = 3m = 1353 = 12513除得的余数c = 8

指数e为负数时可使用扩展欧几里得算法找到b模除m模逆元d来执行模幂运算,即:

c = be mod m = de mod m,其中 e < 0bd ≡ 1 (mod m)

即使在整数很大的情况下,上述模幂运算其实也是易于执行的。然而,计算模的离散对数(即在已知bcm时求出指数e)则较为困难。这种类似單向函數的表现使模幂运算可用于加密算法。

直接算法[编辑]

计算模幂的最直接方法是直接算出be,再把结果模除m。假设已知b = 4e = 13,以及m = 497,要求c

c ≡ 413 (mod 497)

可用计算器算得413结果为67,108,864,模除497,可得c等于445。

注意到b只有一位,e也只有两位,但be的值却有8位。

强加密时b通常至少有1024位[1]。考虑b = 5 × 1076e = 17的情况,b的长度为77位,e的长度为2位,但是be的值以十进制表示却已经有1304位。现代计算机虽然可以进行这种计算,但计算速度却大大降低。

用这种算法求模幂所需的时间取决于操作环境和处理器,时间复杂度为O(e)

内存优化[编辑]

这种方法比第一种所需要的步骤更多,但所需内存和时间均大为减少,其原理为: 给定两个整数ab,以下两个等式是等价的

c mod m = (ab) mod m
c mod m = [(a mod m) ⋅ (b mod m)] mod m

算法如下:

  1. c = 1e′ = 0
  2. e′自增1。
  3. c = (b ⋅ c) mod m.
  4. e′ < e,则返回第二步;否则,c即为cbe (mod m)

再以b = 4e = 13m = 497为例说明,算法第三步需要执行13次:

  • e′ = 1. c = (1 ⋅ 4) mod 497 = 4 mod 497 = 4.
  • e′ = 2. c = (4 ⋅ 4) mod 497 = 16 mod 497 = 16.
  • e′ = 3. c = (16 ⋅ 4) mod 497 = 64 mod 497 = 64.
  • e′ = 4. c = (64 ⋅ 4) mod 497 = 256 mod 497 = 256.
  • e′ = 5. c = (256 ⋅ 4) mod 497 = 1024 mod 497 = 30.
  • e′ = 6. c = (30 ⋅ 4) mod 497 = 120 mod 497 = 120.
  • e′ = 7. c = (120 ⋅ 4) mod 497 = 480 mod 497 = 480.
  • e′ = 8. c = (480 ⋅ 4) mod 497 = 1920 mod 497 = 429.
  • e′ = 9. c = (429 ⋅ 4) mod 497 = 1716 mod 497 = 225.
  • e′ = 10. c = (225 ⋅ 4) mod 497 = 900 mod 497 = 403.
  • e′ = 11. c = (403 ⋅ 4) mod 497 = 1612 mod 497 = 121.
  • e′ = 12. c = (121 ⋅ 4) mod 497 = 484 mod 497 = 484.
  • e′ = 13. c = (484 ⋅ 4) mod 497 = 1936 mod 497 = 445.

因此最终结果c为445,与第一种方法所求结果相等。

与第一种方法相同,这种算法需要O(e)的时间才能完成。但是,由于在计算过程中处理的数字比第一种算法小得多,因此计算时间至少减少了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表示成二进制,即:

此时e的长度为n位。对任意i0 ≤ i < n),ai可取0或1任一值。由定义有an − 1 = 1

be的值可写作:

因此答案c即为:

伪代码[编辑]

下述伪代码基于布魯斯·施奈爾所著《应用密码学》[2]。其中baseexponentmodulus分别对应上式中的bem

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。在第三行代码中重复执行平方运算,会确保在每次循环结束时,变量base等于b2i mod m,其中i是循环执行次数。

本例中,底数b的指数为。 指数用二进制表示为1101,有4位,故循环执行4次。 4位数字从右到左依次为1,0,1,1。

首先,初始化结果为1,并将b的值保存在变量x中:

.
第1步 第1位为1,故令
第2步 第2位为0,故不给R赋值;
第3步 第3位为1,故令
第4步 第4位为1,故令
这是最后一步,所以不需要对x求平方。

综上,R

以下计算次方对497求模的结果。

初始化:

第1步 第1位为1,故令
第2步 第2位为0,故不给R赋值;
第3步 第3位为1,故令
第4步 第4位为1,故令

综上,R,与先前算法中所得结果相同。

该算法时间复杂度为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]. 
  2. ^ Schneier 1996, p. 244.

外部链接[编辑]