模幂

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

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

例如,给定被13除得的余数

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

,其中

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

直接算法

计算模幂的最直接方法是直接算出 ,再把结果模除 。假设已知  ,以及 ,要求 

 

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

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

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

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

内存优化

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

 
 

算法如下:

  1.   
  2.  自增1。
  3.  .
  4.  ,则返回第二步;否则, 即为 

再以   为例说明,算法第三步需要执行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.

外部链接