function modular_pow(base, exponent, modulus) if modulus = 1 thenreturn 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
function modPow(b,e,m) if m == 1 thenreturn 0 elselocal r = 1 b = b % m while e > 0 doif e % 2 == 1 then r = (r*b) % m end e = e >> 1 --Lua 5.2或更早版本使用e = math.floor(e / 2) b = (b^2) % m endreturn r endend
Paul Garrett, Fast Modular Exponentiation Java Applet (页面存档备份,存于互联网档案馆)
Gordon, Daniel M. A Survey of Fast Exponentiation Methods (PDF). Journal of Algorithms (Elsevier BV). 1998, 27 (1): 129–146 [2019-11-30]. ISSN 0196-6774. doi:10.1006/jagm.1997.0913. (原始内容 (PDF)于2019-08-27).
四月 01, 2023
模幂, 英語, modular, exponentiation, 是一种对模进行的冪运算, 在计算机科学, 尤其是公开密钥加密方面有一定用途, 运算是指求整数b, displaystyle, 的e, displaystyle, 次方b, displaystyle, 被正整数m, displaystyle, 所除得到的余数c, displaystyle, 的过程, 可用数学符号表示为c, displaystyle, bmod, 由c, displaystyle, 的定义可得0, displaystyle, 例如, 给. 模幂 英語 modular exponentiation 是一种对模进行的冪运算 在计算机科学 尤其是公开密钥加密方面有一定用途 模幂运算是指求整数b displaystyle b 的e displaystyle e 次方b e displaystyle b e 被正整数m displaystyle m 所除得到的余数c displaystyle c 的过程 可用数学符号表示为c b e mod m displaystyle c b e bmod m 由c displaystyle c 的定义可得0 c lt m displaystyle 0 leq c lt m 例如 给定b 5 displaystyle b 5 e 3 displaystyle e 3 和m 13 displaystyle m 13 5 3 125 displaystyle 5 3 125 被13除得的余数c 8 displaystyle c 8 指数e displaystyle e 为负数时可使用扩展欧几里得算法找到b displaystyle b 模除m displaystyle m 的模逆元d displaystyle d 来执行模幂运算 即 c b e mod m d e mod m displaystyle c b e bmod m d e bmod m 其中 e lt 0 displaystyle e lt 0 且b d 1 mod m displaystyle b cdot d equiv 1 pmod m 即使在整数很大的情况下 上述模幂运算其实也是易于执行的 然而 计算模的离散对数 即在已知b displaystyle b c displaystyle c 和m displaystyle m 时求出指数e displaystyle e 则较为困难 这种类似單向函數的表现使模幂运算可用于加密算法 目录 1 直接算法 2 内存优化 3 从右到左二位算法 3 1 伪代码 3 2 Lua实现 4 软件实现 5 另见 6 参考资料 7 外部链接直接算法 编辑计算模幂的最直接方法是直接算出b e displaystyle b e 再把结果模除m displaystyle m 假设已知b 4 displaystyle b 4 e 13 displaystyle e 13 以及m 497 displaystyle m 497 要求c displaystyle c c 4 13 mod 497 displaystyle c equiv 4 13 pmod 497 可用计算器算得413结果为67 108 864 模除497 可得c 等于445 注意到b displaystyle b 只有一位 e displaystyle e 也只有两位 但b e displaystyle b e 的值却有8位 强加密时b displaystyle b 通常至少有1024位 1 考虑b 5 10 76 displaystyle b 5 times 10 76 和e 17 displaystyle e 17 的情况 b displaystyle b 的长度为77位 e displaystyle e 的长度为2位 但是b e displaystyle b e 的值以十进制表示却已经有1304位 现代计算机虽然可以进行这种计算 但计算速度却大大降低 用这种算法求模幂所需的时间取决于操作环境和处理器 时间复杂度为O e displaystyle mathrm O e 内存优化 编辑这种方法比第一种所需要的步骤更多 但所需内存和时间均大为减少 其原理为 给定两个整数a displaystyle a 和b displaystyle b 以下两个等式是等价的 c mod m a b mod m displaystyle c bmod m a cdot b bmod m c mod m a mod m b mod m mod m displaystyle c bmod m a bmod m cdot b bmod m bmod m 算法如下 令c 1 displaystyle c 1 e 0 displaystyle e 0 e displaystyle e 自增1 令c b c mod m displaystyle c b cdot c bmod m 若e lt e displaystyle e lt e 则返回第二步 否则 c displaystyle c 即为c b e mod m displaystyle c equiv b e pmod m 再以b 4 displaystyle b 4 e 13 displaystyle e 13 m 497 displaystyle m 497 为例说明 算法第三步需要执行13次 e 1 c 1 4 mod 4 97 4 mod 4 97 4 displaystyle e 1 cdot c 1 cdot 4 bmod 4 97 4 bmod 4 97 4 e 2 c 4 4 mod 4 97 16 mod 4 97 16 displaystyle e 2 cdot c 4 cdot 4 bmod 4 97 16 bmod 4 97 16 e 3 c 16 4 mod 4 97 64 mod 4 97 64 displaystyle e 3 cdot c 16 cdot 4 bmod 4 97 64 bmod 4 97 64 e 4 c 64 4 mod 4 97 256 mod 4 97 256 displaystyle e 4 cdot c 64 cdot 4 bmod 4 97 256 bmod 4 97 256 e 5 c 256 4 mod 4 97 1024 mod 4 97 30 displaystyle e 5 cdot c 256 cdot 4 bmod 4 97 1024 bmod 4 97 30 e 6 c 30 4 mod 4 97 120 mod 4 97 120 displaystyle e 6 cdot c 30 cdot 4 bmod 4 97 120 bmod 4 97 120 e 7 c 120 4 mod 4 97 480 mod 4 97 480 displaystyle e 7 cdot c 120 cdot 4 bmod 4 97 480 bmod 4 97 480 e 8 c 480 4 mod 4 97 1920 mod 4 97 429 displaystyle e 8 cdot c 480 cdot 4 bmod 4 97 1920 bmod 4 97 429 e 9 c 429 4 mod 4 97 1716 mod 4 97 225 displaystyle e 9 cdot c 429 cdot 4 bmod 4 97 1716 bmod 4 97 225 e 10 c 225 4 mod 4 97 900 mod 4 97 403 displaystyle e 10 cdot c 225 cdot 4 bmod 4 97 900 bmod 4 97 403 e 11 c 403 4 mod 4 97 1612 mod 4 97 121 displaystyle e 11 cdot c 403 cdot 4 bmod 4 97 1612 bmod 4 97 121 e 12 c 121 4 mod 4 97 484 mod 4 97 484 displaystyle e 12 cdot c 121 cdot 4 bmod 4 97 484 bmod 4 97 484 e 13 c 484 4 mod 4 97 1936 mod 4 97 445 displaystyle e 13 cdot c 484 cdot 4 bmod 4 97 1936 bmod 4 97 445 因此最终结果c displaystyle c 为445 与第一种方法所求结果相等 与第一种方法相同 这种算法需要O e displaystyle mathrm O e 的时间才能完成 但是 由于在计算过程中处理的数字比第一种算法小得多 因此计算时间至少减少了O e displaystyle mathrm 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 displaystyle e 表示成二进制 即 e i 0 n 1 a i 2 i displaystyle e sum i 0 n 1 a i 2 i 此时e displaystyle e 的长度为n displaystyle n 位 对任意i displaystyle i 0 i lt n displaystyle 0 leq i lt n a i displaystyle a i 可取0或1任一值 由定义有a n 1 1 displaystyle a n 1 1 b e displaystyle b e 的值可写作 b e b i 0 n 1 a i 2 i i 0 n 1 b 2 i a i displaystyle 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 因此答案c displaystyle c 即为 c i 0 n 1 b 2 i a i mod m displaystyle c equiv prod i 0 n 1 left b 2 i right a i mbox mod m 伪代码 编辑 下述伪代码基于布魯斯 施奈爾所著 应用密码学 2 其中base exponent和modulus分别对应上式中的b displaystyle b e displaystyle e 和m displaystyle m 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 gt 0 if exponent mod 2 1 result result base mod modulus exponent exponent gt gt 1 base base base mod modulus return result 注意到在首次进入循环时 变量base等于b displaystyle b 在第三行代码中重复执行平方运算 会确保在每次循环结束时 变量base等于b 2 i mod m displaystyle b 2 i bmod m 其中i displaystyle i 是循环执行次数 本例中 底数b displaystyle b 的指数为e 13 displaystyle e 13 指数用二进制表示为1101 有4位 故循环执行4次 4位数字从右到左依次为1 0 1 1 首先 初始化结果R displaystyle R 为1 并将b 的值保存在变量x displaystyle x 中 R 1 b 0 且 x b displaystyle R leftarrow 1 b 0 text 且 x leftarrow b 第1步 第1位为1 故令R R x b 1 displaystyle R leftarrow R cdot x text b 1 令x x 2 b 2 displaystyle x leftarrow x 2 text b 2 dd 第2步 第2位为0 故不给R 赋值 令x x 2 b 4 displaystyle x leftarrow x 2 text b 4 dd 第3步 第3位为1 故令R R x b 5 displaystyle R leftarrow R cdot x text b 5 令x x 2 b 8 displaystyle x leftarrow x 2 text b 8 dd 第4步 第4位为1 故令R R x b 13 displaystyle R leftarrow R cdot x text b 13 这是最后一步 所以不需要对x 求平方 dd 综上 R displaystyle R 为b 13 displaystyle b 13 以下计算b 4 displaystyle b 4 的e 13 displaystyle e 13 次方对497求模的结果 初始化 R 1 b 0 displaystyle R leftarrow 1 b 0 且x b 4 displaystyle x leftarrow b 4 第1步 第1位为1 故令R R 4 mod 497 4 mod 497 displaystyle R leftarrow R cdot 4 pmod 497 equiv 4 pmod 497 令x x 2 b 2 4 2 16 mod 497 displaystyle x leftarrow x 2 text b 2 equiv 4 2 equiv 16 pmod 497 dd 第2步 第2位为0 故不给R 赋值 令x x 2 b 4 16 2 mod 497 256 mod 497 displaystyle x leftarrow x 2 text b 4 equiv 16 2 pmod 497 equiv 256 pmod 497 dd 第3步 第3位为1 故令R R x b 5 4 256 mod 497 30 mod 497 displaystyle R leftarrow R cdot x text b 5 equiv 4 cdot 256 pmod 497 equiv 30 pmod 497 令x x 2 b 8 256 2 mod 497 429 mod 497 displaystyle x leftarrow x 2 text b 8 equiv 256 2 pmod 497 equiv 429 pmod 497 dd 第4步 第4位为1 故令R R x b 13 30 429 mod 497 445 mod 497 displaystyle R leftarrow R cdot x text b 13 equiv 30 cdot 429 pmod 497 equiv 445 pmod 497 综上 R displaystyle R 为4 13 mod 497 445 mod 497 displaystyle 4 13 pmod 497 equiv 445 pmod 497 与先前算法中所得结果相同 该算法时间复杂度为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 gt 0 do if e 2 1 then r r b m end e e gt gt 1 Lua 5 2或更早版本使用e math floor e 2 b b 2 m end return r end end软件实现 编辑鉴于模幂运算是计算机科学中的重要操作 并且已有高效算法 所以许多编程语言和高精度整数库都有执行模幂运算的函数 Python内置的pow 求幂 函数 1 页面存档备份 存于互联网档案馆 NET框架的BigInteger类的ModPow 方法 Java的java math BigInteger类的modPow 方法 Perl的Math BigInt模块的bmodpow 方法 2 页面存档备份 存于互联网档案馆 Raku内置的expmod例程 Go的big Int类的Exp 求幂 方法 3 页面存档备份 存于互联网档案馆 PHP的BC Math库的bcpowmod 函数 4 页面存档备份 存于互联网档案馆 GNU多重精度运算库 GMP 的mpz powm 函数 5 页面存档备份 存于互联网档案馆 FileMaker Pro的 PowerMod 函数 以1024位RSA加密为例 Ruby的openssl包的OpenSSL BN mod exp方法 6 页面存档备份 存于互联网档案馆 HP Prime计算器的CAS powmod 函数 7 另见 编辑蒙哥马利算法 用于计算模很大时的余数 参考资料 编辑 Weak Diffie Hellman and the Logjam Attack weakdh org 2019 05 03 原始内容存档于2021 03 29 Schneier 1996 p 244 外部链接 编辑Schneier Bruce Applied Cryptography Protocols Algorithms and Source Code in C Second Edition 2nd Wiley 1996 ISBN 978 0 471 11709 4 Paul Garrett Fast Modular Exponentiation Java Applet 页面存档备份 存于互联网档案馆 Gordon Daniel M A Survey of Fast Exponentiation Methods PDF Journal of Algorithms Elsevier BV 1998 27 1 129 146 2019 11 30 ISSN 0196 6774 doi 10 1006 jagm 1997 0913 原始内容存档 PDF 于2019 08 27 取自 https zh wikipedia org w index php title 模幂 amp oldid 75827938, 维基百科,wiki,书籍,书籍,图书馆,