https://en.wikipedia.org/wiki/Modular_exponentiation

?

蒙哥馬利(Montgomery)冪模運(yùn)算是快速計(jì)算a^b%k的一種算法，是RSA加密算法的核心之一。

蒙哥馬利模乘的優(yōu)點(diǎn)在于減少了取模的次數(shù)（在大數(shù)的條件下）以及簡(jiǎn)化了除法的復(fù)雜度（在2的k次冪的進(jìn)制下除法僅需要進(jìn)行左移操作）。模冪運(yùn)算是RSA 的核心算法，最直接地決定了RSA 算法的性能。 針對(duì)快速模冪運(yùn)算這一課題，西方現(xiàn)代數(shù)學(xué)家提出了大量的解決方案，通常都是先將冪模運(yùn)算轉(zhuǎn)化為乘模運(yùn)算。

Modular exponentiation?is a type of?exponentiation取冪，求冪；乘方?performed over a?modulus模數(shù)，系數(shù).

It is useful in?computer science, especially in the field of?public-key cryptography.

?

The operation of modular exponentiation calculates the remainder when an integer?b?底數(shù)(the base) raised to the?eth power (the exponent指數(shù)),?b^e, is divided by a?positive integer?m?(the modulus).

In symbols, given base?b, exponent?e, and modulus?m, the modular exponentiation?c?is:?c?≡?b^e?(mod?m). ? ? ? ?//c=b的e次方 %m

?

For example, given?b?= 5,?e?= 3?and?m?= 13, the solution?c?= 8?is the remainder of dividing?5³?= 125?by 13. ? ? ?//c=5^3%13=125%13 ? 因?yàn)?25=13*9+8 ，所以125對(duì)13求余，結(jié)果是8

?

Given integers?b?and?e, and a positive integer?m, a unique solution?c?exists with the property?0 ≤?c?<?m.

Modular exponentiation can be performed with a?negative?exponent?e?by finding the?modular multiplicative inverse?d?of?b?modulo?m?using the?extended Euclidean algorithm. That is:

c?≡?b^e?≡?d^?e?mod?m?where?e?< 0?and?b???d?≡ 1 mod?m.

Modular exponentiation similar to the one described above are considered easy to compute, even when the numbers involved are enormous巨大的.

On the other hand, computing the?discrete logarithm離散對(duì)數(shù)?– that is, the task of finding the exponente?when given?b,?c, and?m?– is believed to be difficult.

This?one-way function?behavior makes modular exponentiation a candidate for use in cryptographic algorithms.

?

?

?

?

?

?

?

轉(zhuǎn)載于:https://www.cnblogs.com/chucklu/p/5309297.html

總結(jié)

以上是生活随笔為你收集整理的Modular_exponentiation模幂运算的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。