# 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:

1. 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$$).
2. 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$$:

1. Convert $$17$$ to binary: $$(17)_2=10001$$
2. 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$$