Example

To compute the modular exponentiation \( 9^{10} \mod 7 \):

1] Convert the exponent to binary: \( (10)_2 = 1010 \).

2] Construct the table using the formula \( c_i = c_{i-1}^2 \cdot \text{base}^{\text{bit}} \), reading the binary number from left to right, starting with \( c_0=1 \). In this example, the base is 9 and the modulus is 7.

$ (10)_2 $	$ c_0 = 1 $
1	$ c_1 \equiv (1^2 \cdot 9^1) \mod 7 $ = $ \color{red}2 $
0	$ c_2 \equiv (\color{red}{2}^2 \cdot 9^0) \mod 7 $ = $ \color{blue}4 $
1	$ c_3 \equiv (\color{blue}{4}^2 \cdot 9^1) \mod 7 $ = $ \color{magenta}4 $
0	$ c_4 \equiv (\color{magenta}{4}^2 \cdot 9^0) \mod 7 $ = $ \color{green}2 $

The last value \( c_4 \) is the result of the congruence:

$$ 9^{10} \equiv 2 \mod 7 $$