Modular Exponentiation

Modular Exponentiatio>

To compute modular exponentiation using congruences, $$ a^m \mod n $$, I can follow this approach:

Compute all powers $ a^x $ where $ x = 2^k $ and $ x < m $.
Express the exponent $ m $ in binary (base 2).
Identify the product of the powers $ a^x $ that correspond to the 1s in the binary representation of $ m $.
Compute the powers and their product while reducing the intermediate results modulo $ n $ at each step.

The final result is $ a^m $ modulo $ n $.

A Practical Example

Let's compute $ a^m $ with $ a = 3 $ and $ m = 29 $ modulo 7:

$$ 3^{29} \mod 7 $$

First, I compute all powers where the exponent is $ 2^k $ and less than $ m = 29 $:

$$ 3^{2^0} \mod 7 \text{ since } 2^0=1 < 29$$

$$ 3^{2^1} \mod 7 \text{ since } 2^1=2 < 29 $$

$$ 3^{2^2} \mod 7 \text{ since } 2^2=4 < 29 $$

$$ 3^{2^3} \mod 7 \text{ since } 2^3=8 < 29 $$

$$ 3^{2^4} \mod 7 \text{ since } 2^4=16 < 29 $$

I stop here because $ 2^5 = 32 > 29 $.

This gives the following congruences:

$$ 3^{2^0} \mod 7 $$

$$ 3^{2^1} \mod 7 $$

$$ 3^{2^2} \mod 7 $$

$$ 3^{2^3} \mod 7 $$

$$ 3^{2^4} \mod 7 $$

Next, I write $ m = 29 $ in binary:

$$ (11101)_{29} $$

Each binary digit (starting from the right) corresponds to a power of $ a $.

modular exponentiation

Now, I form a product using only the powers associated with the 1s in the binary representation:

$$ 3^{2^4} \cdot 3^{2^3} \cdot 3^{2^2} \cdot 3^{2^0} \mod 7 $$

Computing the powers:

$$ 3^{16} \cdot 3^8 \cdot 3^4 \cdot 3^1 \mod 7 $$

$$ 43046721 \cdot 6561 \cdot 81 \cdot 3 \mod 7 $$

Note: If any power is still too large to compute directly, I can simplify it or use the same algorithm recursively. For example, $ 3^{16} $ is difficult to compute directly, but I can break it down as follows: $$ 3^{16} = (3^4)^4 \mod 7 $$ $$ 3^{16} = 81^4 \mod 7$$ Since $ 81 $ divided by 7 leaves a remainder of 4, I rewrite the equation modulo 7: $$ 3^{16} = 4^4 \mod 7$$ $$ 3^{16} = 16^2 \mod 7$$ Since $ 16 $ divided by 7 leaves a remainder of 2, I simplify further: $$ 3^{16} = 2^2 \mod 7$$ $$ 3^{16} = 4 \mod 7$$ This allows me to express $ 3^{16} $ directly in modulo 7 without calculating its decimal value.

Now, I reduce all values modulo 7:

$$ 4 \cdot 2 \cdot 4 \cdot 3 \mod 7 $$

I simplify step by step, reducing intermediate results modulo 7 whenever they exceed 7:

$$ 4 \cdot 2 \cdot 4 \cdot 3 \mod 7 $$

$$ 1 \cdot 4 \cdot 3 \mod 7 $$

$$ 4 \cdot 3 \mod 7 $$

$$ 5 \mod 7 $$

This gives the final result:

$$ 3^{29} \mod 7 $$

$$ 5 \mod 7 $$

Thus, $ 3^{29} $ modulo 7 is equivalent to 5 modulo 7:

$$ 3^{29} \equiv 5 \mod 7 $$

And that's it.