PowerMod Calculator
How to calculate ab mod n
There are several ways to compute \(a^b \, \text{mod} \, n\). The most efficient method consists of:
- divide the exponent \(b\) into powers of 2 by writing it in binary, obtaining
\(b = (d_{k-1},d_{k-2},...,d_1,d_0\)).
- build the following table:
\begin{array} {c|c}
(b)_2 & c_0 = 1 \\
\hline
d_{k-1} & c_1 \equiv c_0^2 \cdot a^{d_{k-1}} \, \text{mod} \, n \\
\hline
d_{k-2} & c_2 \equiv c_1^2 \cdot a^{d_{k-2}} \, \text{mod} \, n \\
\hline
\vdots & \vdots \\
\vdots & \vdots \\
\hline
d_1 & c_{k-1} \equiv c_{k-2}^2 \cdot a^{d_1} \, \text{mod} \, n \\
\hline
d_0 & c_k \equiv c_{k-1}^2 \cdot a^{d_0} \, \text{mod} \, n \\
\end{array}
Result: \(a^b \equiv c_k \, \text{mod} \, n \)
Online tool to compute modular exponentiation
This tool allows you to solve online modular exponentiation step-by-step.
The numbers entered must be positive integers except for the base, that may be negative too, and
the modulo, that must only be greater than zero.
Example
Assuming we must calculate \(3^{17} \, \text{mod} \, 25\):
- Convert \(17\) to binary: \((17)_2=10001\)
- Make the table:
\begin{array} {c|l}
(17)_2 & c_0=1 \\
\hline
1 & c_1 \equiv1^2 \cdot 3^1 = 1 \cdot 3 = 3\, \text{mod} \,25 \\
\hline
0 & c_2 \equiv3^2 \cdot 3^0 = 9 \cdot 1 = 9\, \text{mod} \,25 \\
\hline
0 & c_3 \equiv9^2 \cdot 3^0 = 81 \cdot 1 = 81 \equiv 6\, \text{mod} \,25 \\
\hline
0 & c_4 \equiv6^2 \cdot 3^0 = 36 \cdot 1 = 36 \equiv 11\, \text{mod} \,25 \\
\hline
1 & c_5 \equiv11^2 \cdot 3^1 = 121 \cdot 3 = 363 \equiv 13\, \text{mod} \,25 \\
\end{array}
Result: \(3^{17} \equiv 13\, \text{mod} \,25 \)
