模幂維基百科,自由的 encyclopedia 模幂(英語: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 < m {\displaystyle 0\leq c<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 < 0 {\displaystyle e<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} )则较为困难。这种类似單向函數的表现使模幂运算可用于加密算法。
模幂(英語: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 < m {\displaystyle 0\leq c<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 < 0 {\displaystyle e<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} )则较为困难。这种类似單向函數的表现使模幂运算可用于加密算法。