Fast Modular Exponentiation

Step-by-Step Animation Animation Speed

Elaboration:

?

Fast Modular Exponentiation (b^e % n): This algorithm is commonly used in public key cryptography. In cryptography, base b and power e are both large numbers. Multiplying b by itself (e - 1) times is not practical.

Algorithm Details: The last equation shows the pattern of repeatedly squaring b

e = e_i · 2ⁱ + e_{i - 1} · 2^{i - 1} + e_{i - 2} · 2^{i - 2} + ··· + e₁ · 2¹ + e₀ · 2⁰ where e_i is the i_th bit of e

b ^e % n = ( b ^{e_i · 2ⁱ + e_{i - 1} · 2^{i - 1} + e_{i - 2} · 2^{i - 2} + ··· + e₁ · 2¹ + e₀ · 2⁰}) % n

b ^e % n = ( b^{e_i · 2ⁱ} · b^{e_{i - 1} · 2^{i - 1}} · b^{e_{i - 2} · 2^{i - 2}} · ··· · b^{e₁ · 2¹} · b^{e₀ · 2⁰} ) % n

快速模块化求幂定义：快速模块化求幂实现的最基本的理论的引理就是积的取余等于取余的积的取余。在在这条引理的基础之上，对指数型数据进行拆分以及合并，从而得到我们用的快速幂算法。

按键说明：

Compute b^e % n 在三个文本框中分别输入b，e，n三个数值，并点击此按钮计算得到b的e次方并对n进行取余。