查看“︁模幂”︁的源代码

{{NoteTA
|G1 = Math
|G2 = IT
}}
'''模幂'''（{{lang-en|modular exponentiation}}）是一种对[[模算數|模]]进行的[[冪]]运算，在[[计算机科学]]，尤其是[[公开密钥加密]]方面有一定用途。

模幂运算是指求整数<math>b</math>的<math>e</math>次方<math>b^e</math>被[[正整数]]<math>m</math>所除得到的余数<math>c</math>的过程，可用数学符号表示为<math>c=b^e \bmod m</math>。由<math>c</math>的定义可得<math>0\leq c <m</math>。

例如，给定<math>b=5</math>，<math>e=3</math>和<math>m=13</math>，<math>5^3=125</math>被13除得的余数<math>c=8</math>。

指数<math>e</math>为负数时可使用[[扩展欧几里得算法]]找到<math>b</math>模除<math>m</math>的[[模逆元]]<math>d</math>来执行模幂运算，即：

: <math>c=b^e \bmod m=d^{-e} \bmod m</math>，其中 <math>e<0</math>且<math>b\cdot d \equiv 1 \pmod{m}</math>。

即使在整数很大的情况下，上述模幂运算其实也是易于执行的。然而，计算模的[[离散对数]]（即在已知<math>b</math>，<math>c</math>和<math>m</math>时求出指数<math>e</math>）则较为困难。这种类似[[單向函數]]的表现使模幂运算可用于加密算法。

== 直接算法 ==
计算模幂的最直接方法是直接算出<math>b^e</math>，再把结果模除<math>m</math>。假设已知<math>b=4</math>，<math>e=13</math>，以及<math>m=497</math>，要求<math>c</math>：

: <math>c\equiv 4^{13}\pmod{497}</math>

可用计算器算得4<sup>13</sup>结果为67,108,864，模除497，可得{{math|''c''}}等于445。

注意到<math>b</math>只有一位，<math>e</math>也只有两位，但<math>b^e</math>的值却有8位。

强加密时<math>b</math>通常至少有1024位<ref>{{Cite web|title=Weak Diffie-Hellman and the Logjam Attack|url=https://weakdh.org/|website=weakdh.org|access-date=2019-05-03|archive-date=2021-03-29|archive-url=https://web.archive.org/web/20210329172612/https://weakdh.org/|dead-url=no}}</ref>。考虑<math>b=5\times 10^{76}</math>和<math>e=17</math>的情况，<math>b</math>的长度为77位，<math>e</math>的长度为2位，但是<math>b^e</math>的值以[[十进制]]表示却已经有1304位。现代计算机虽然可以进行这种计算，但计算速度却大大降低。

用这种算法求模幂所需的时间取决于操作环境和处理器，时间复杂度为<math>\mathrm{O}(e)</math>。

== 空間优化 ==
这种方法比第一种所需要的步骤更多，但所需内存空間和时间均大为减少，其原理为：
给定两个整数<math>a</math>和<math>b</math>，以下两个等式是[[模除#等价性|等价的]]{{Broken anchor|date=2024-10-16|bot=User:Cewbot/log/20201008/configuration|target_link=模除#等价性|reason= 錨點（等价性）[[Special:Diff/84609222|已被刪除]]。}}：

: <math>c \bmod m=(a\cdot b) \bmod m</math>
: <math>c \bmod m=[(a \bmod m)\cdot (b \bmod m)]\bmod m</math>

算法如下：

# 令<math>c=1</math>，<math>e'=0</math>。
# <math>e'</math>自增1。
# 令<math>c=(b\cdot c) \bmod m</math>.
# 若<math>e'<e</math>，则返回第二步；否则，<math>c</math>即为<math>c\equiv b^e \pmod{m}</math>。

再以<math>b=4</math>，<math>e=13</math>，<math>m=497</math>为例说明，算法第三步需要执行13次：

* <math>e' = 1\cdot c=(1\cdot 4) \bmod 497=4 \bmod 497=4</math>
* <math>e' = 2\cdot c=(4\cdot 4) \bmod 497=16 \bmod 497=16</math>
* <math>e' = 3\cdot c=(16\cdot 4) \bmod 497=64 \bmod 497=64</math>
* <math>e' = 4\cdot c=(64\cdot 4) \bmod 497=256 \bmod 497=256</math>
* <math>e' = 5\cdot c=(256\cdot 4) \bmod 497=1024 \bmod 497=30</math>
* <math>e' = 6\cdot c=(30\cdot 4) \bmod 497=120 \bmod 497=120</math>
* <math>e' = 7\cdot c=(120\cdot 4) \bmod 497=480 \bmod 497=480</math>
* <math>e' = 8\cdot c=(480\cdot 4) \bmod 497=1920 \bmod 497=429</math>
* <math>e' = 9\cdot c=(429\cdot 4) \bmod 497=1716 \bmod 497=225</math>
* <math>e' = 10\cdot c=(225\cdot 4) \bmod 497=900 \bmod 497=403</math>
* <math>e' = 11\cdot c=(403\cdot 4) \bmod 497=1612 \bmod 497=121</math>
* <math>e' = 12\cdot c=(121\cdot 4) \bmod 497=484 \bmod 497=484</math>
* <math>e' = 13\cdot c=(484\cdot 4) \bmod 497=1936 \bmod 497=445</math>

因此最终结果<math>c</math>为445，与第一种方法所求结果相等。

与第一种方法相同，这种算法需要<math>\mathrm{O}(e)</math>的时间才能完成。但是，由于在计算过程中处理的数字比第一种算法小得多，因此计算时间至少减少了<math>\mathrm{O}(e)</math>倍。

算法伪代码如下：
 '''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

== 从右到左二位算法 ==
第三种方法结合了第二种算法和[[平方求幂]]原理，使所需步骤大大减少，同时也与第二种方法一样减少了内存占用量。

首先把<math>e</math>表示成[[二进制]]，即：

: <math>e = \sum_{i=0}^{n-1} a_i 2^i</math>

此时<math>e</math>的长度为<math>n</math>位。对任意<math>i</math>（<math>0\leq i < n</math>），<math>a_i</math>可取0或1任一值。由定义有<math>a_{n-1}=1</math>。

<math>b^e</math>的值可写作：

: <math>b^e = b^{\left( \sum_{i=0}^{n-1} a_i 2^i \right)} = \prod_{i=0}^{n-1} \left( b^{2^i} \right) ^ {a_i}</math>

因此答案<math>c</math>即为：

: <math>c \equiv \prod_{i=0}^{n-1} \left( b^{2^i} \right) ^ {a_i}\ (\mbox{mod}\ m)</math>

=== 伪代码 ===

下述伪代码基于[[布魯斯·施奈爾]]所著《应用密码学》<ref name="schneier96p244">[[#Schneier96|Schneier 1996]], p. 244.</ref>。其中<var>base</var>，<var>exponent</var>和<var>modulus</var>分别对应上式中的<math>b</math>，<math>e</math>和<math>m</math>。

 '''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

注意到在首次进入循环时，变量<var>base</var>等于<math>b</math>。在第三行代码中重复执行平方运算，会确保在每次循环结束时，变量<var>base</var>等于<math>b^{2^i} \bmod m</math>，其中<math>i</math>是循环执行次数。

本例中，底数<math>b</math>的指数为<math>e = 13</math>。
指数用二进制表示为1101，有4位，故循环执行4次。
4位数字从右到左依次为1，0，1，1。

首先，初始化结果<math>R</math>为1，并将{{math|''b''}}的值保存在变量<math>x</math>中：
: <math> R \leftarrow 1 \, ( = b^0) \text{且 } x \leftarrow b </math>.
: 第1步  第1位为1，故令<math> R \leftarrow R \cdot x \text{ }(= b^1) </math>；
:: 令<math> x \leftarrow x^2 \text{ }(= b^2) </math>。
: 第2步  第2位为0，故不给{{math|''R''}}赋值；
:: 令<math> x \leftarrow x^2 \text{ }(= b^4) </math>。
: 第3步  第3位为1，故令<math> R \leftarrow R \cdot x \text{ }(= b^5) </math>；
:: 令<math> x \leftarrow x^2 \text{ }(= b^8) </math>。
: 第4步  第4位为1，故令<math> R \leftarrow R \cdot x \text{ }(= b^{13}) </math>；
:: 这是最后一步，所以不需要对{{math|''x''}}求平方。
综上，<math>R</math>为<math>b^{13}</math>。

以下计算<math>b = 4</math>的<math>e = 13</math>次方对497求模的结果。

初始化：
: <math> R \leftarrow 1 \, ( = b^0) </math>且<math> x \leftarrow b = 4 </math>。
: 第1步  第1位为1，故令<math>R \leftarrow R \cdot 4 \pmod {497} \equiv 4 \pmod{497} </math>；
:: 令<math> x \leftarrow x^2 \text{ }(= b^2) \equiv 4^2 \equiv 16 \pmod{497} </math>。
: 第2步  第2位为0，故不给{{math|''R''}}赋值；
:: 令<math> x \leftarrow x^2 \text{ }(= b^4) \equiv 16^2 \pmod{497} \equiv 256 \pmod{497} </math>。
: 第3步  第3位为1，故令<math> R \leftarrow R \cdot x \text{ }(= b^5) \equiv 4 \cdot 256 \pmod{497} \equiv 30 \pmod{497} </math>；
:: 令<math> x \leftarrow x^2 \text{ }(= b^8) \equiv 256^2 \pmod{497} \equiv 429 \pmod{497} </math>。
: 第4步  第4位为1，故令<math> R \leftarrow R \cdot x \text{ }(= b^{13}) \equiv 30 \cdot 429 \pmod{497} \equiv 445 \pmod{497} </math>；

综上，<math>R</math>为<math>4^{13} \pmod{497} \equiv 445 \pmod{497}</math>，与先前算法中所得结果相同。

该算法时间复杂度为{{math|O(log }}<var>exponent</var>{{math|)}}。指数<var>exponent</var>值较大时，这种算法与前两种{{math|O(}}<var>exponent</var>{{math|)}}算法相比具有明显的速度优势。例如，如果指数为2<sup>20</sup> = 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'''

== 软件实现 ==
鉴于模幂运算是计算机科学中的重要操作，并且已有高效算法，所以许多编程语言和高精度整数库都有执行模幂运算的函数：
* [[Python]]内置的<code>pow()</code>（求幂）函数[https://docs.python.org/library/functions.html#pow] {{Wayback|url=https://docs.python.org/library/functions.html#pow |date=20121027081602 }}
* [[.NET框架]]的<code>BigInteger</code>类的<code>[http://msdn.microsoft.com/en-us/library/system.numerics.biginteger.modpow%28v=vs.100%29.aspx#pow ModPow()]</code>方法
* [[Java]]的<code>java.math.BigInteger</code>类的{{Javadoc:SE|name=modPow()|java/math|BigInteger|modPow(java.math.BigInteger,java.math.BigInteger)}}方法
* [[Perl]]的<code>Math::BigInt</code>模块的<code>bmodpow()</code>方法[http://perldoc.perl.org/Math/BigInt.html#bmodpow%28%29] {{Wayback|url=http://perldoc.perl.org/Math/BigInt.html#bmodpow%28%29 |date=20200605174846 }}
* [[Raku]]内置的<code>expmod</code>例程
* [[Go]]的<code>big.Int</code>类的<code>Exp()</code>（求幂）方法[http://golang.org/pkg/big/#Int.Exp] {{Wayback|url=http://golang.org/pkg/big/#Int.Exp |date=20120325130428 }}
* [[PHP]]的BC Math库的<code>bcpowmod()</code>函数[http://www.php.net/manual/en/function.bcpowmod.php] {{Wayback|url=http://www.php.net/manual/en/function.bcpowmod.php |date=20210118150749 }}
* [[GNU多重精度运算库]]（GMP）的<code>mpz_powm()</code>函数[http://gmplib.org/manual/Integer-Exponentiation.html] {{Wayback|url=http://gmplib.org/manual/Integer-Exponentiation.html |date=20170112181931 }}
* [[FileMaker]] Pro的<code>[http://www.briandunning.com/cf/1482 @PowerMod()]</code>函数（以1024位[[RSA加密]]为例）
* [[Ruby]]的<code>openssl</code>包的<code>OpenSSL::BN#mod_exp</code>方法[http://ruby-doc.org/stdlib-trunk/libdoc/openssl/rdoc/OpenSSL/BN.html#method-i-mod_exp] {{Wayback|url=http://ruby-doc.org/stdlib-trunk/libdoc/openssl/rdoc/OpenSSL/BN.html#method-i-mod_exp |date=20171117070019 }}
* [[HP Prime]]计算器的CAS.powmod()函数[http://h20628.www2.hp.com/km-ext/kmcsdirect/emr_na-c04120022-1.pdf]{{Dead link}}

== 另见 ==

* [[蒙哥马利算法]]，用于计算模很大时的余数。

== 参考资料 ==
{{reflist}}

== 外部链接 ==

* {{cite book|title=Applied Cryptography: Protocols, Algorithms, and Source Code in C, Second Edition|url=https://archive.org/details/Applied_Cryptography_2nd_ed._B._Schneier|last=Schneier|first=Bruce|authorlink=Bruce Schneier|year=1996|publisher=Wiley|edition=2nd|isbn=978-0-471-11709-4|ref=Schneier96}}
* Paul Garrett, [http://www.math.umn.edu/~garrett/crypto/a01/FastPow.html Fast Modular Exponentiation Java Applet] {{Wayback|url=http://www.math.umn.edu/~garrett/crypto/a01/FastPow.html |date=20161024213654 }}
* {{cite journal|title=A Survey of Fast Exponentiation Methods|url=https://www.dmgordon.org/papers/jalg.pdf|last=Gordon|first=Daniel M.|journal=Journal of Algorithms|publisher=Elsevier BV|issue=1|doi=10.1006/jagm.1997.0913|year=1998|volume=27|pages=129–146|issn=0196-6774|access-date=2019-11-30|archive-date=2019-08-27|archive-url=https://web.archive.org/web/20190827044531/https://www.dmgordon.org/papers/jalg.pdf|dead-url=no}}

{{数论算法}}

[[Category:密码算法]]
[[Category:数论算法]]
[[Category:同余]]
[[Category:带有伪代码示例的条目]]