Modular Exponentiation

Context: FIT1058_MOC · computing $a^m\mathrm{mod}n$ fast · square-and-multiply via binary exponent · exponent reduced by Euler’s theorem

Quick Revision

• 🎯 Objective: compute $a^m\mathrm{mod}n$ efficiently ➔ square-and-multiply, $O(\log m)$ multiplications.
• 📦 Core Components: binary exponent ➔ reduce mod $n$ each step ➔ reduce exponent mod $\varphi (n)$.
• ⚡ Key Constraint: easy forward, discrete-log inverse is hard — the One-Way Function basis.

📝 Core

1. Fast Exponentiation

• Naïve ➔ $m-1$ multiplications.
• Square-and-multiply ➔ write $m$ in binary, repeatedly square ⟹ $O(\log m)$.
• Bound ➔ at most $2\lfloor {\log }_{2}m\rfloor$ multiplications.

2. Three Savings

• Fewer multiplications ➔ squaring cuts $m-1\to O(\log m)$.
• Small factors ➔ reduce mod $n$ each step.
• Smaller exponent ➔ $a^m\equiv a^{m\mathrm{mod}\varphi (n)}$ if $\gcd (a,n)=1$ (Euler’s Theorem and Fermat’s Little Theorem).

3. One-Wayness

• Easy ➔ modular exponentiation.
• Hard ➔ inverting it (discrete logarithm) ➔ powers Diffie-Hellman Key Agreement.

Key identities:

$36=2^5+2^2\Rightarrow 3^{36}=3^{32}\cdot 3^4$ $3^2=9,9^2\equiv 6,6^2\equiv 11,11^2\equiv 21(\mathrm{mod}25);\varphi (25)=20\Rightarrow 3^{36}\equiv 3^{16}\equiv 21$

⚖️ Core Decision Matrix

Trick	Effect	Cost
square-and-multiply	$m-1\to O(\log m)$ mults	binary exponent
reduce mod $n$	keep factors $<n$	per step
reduce exp mod $\varphi (n)$	shrink $m$	needs $\gcd (a,n)=1$

When It Flips: three independent savings — fewer multiplications, smaller products, smaller exponent. Modular exponentiation is the workhorse of public-key cryptography precisely because it is easy forward but hard to invert (discrete log).

📊 Exam Execution Trace

Manual Execution Trace

$7^{13}\mathrm{mod}11$, $13=(1101{)}_2$:

Step / State	Power	Value mod 11
0 (Init)	$7^1$	7
1	$7^2$	5
2	$7^4$	3
3	$7^8$	9

⚠️ Common Mistakes

• 💡 Exponent reduction needs coprimality ➔ $a^m\equiv a^{m\mathrm{mod}\varphi (n)}$ requires $\gcd (a,n)=1$; without it the shortcut can fail. Reduce mod $n$ at every step to keep numbers small.

🧠 Active Recall

How does square-and-multiply compute $3^{36}$ in 6 multiplications, and the general bound?

• Hint: Binary exponent.

Answer

• Short answer: $36=2^5+2^2$; five squarings ($3^2,\dots ,3^{32}$) + one multiply, vs 35 naïvely.
• Why: $O(\log m)$ ➔ at most $2\lfloor {\log }_{2}m\rfloor$ multiplications.

Give the two further tricks for $a^m\mathrm{mod}n$ using $3^{36}\mathrm{mod}25$.

• Hint: Reduce products and exponent.

Answer

• Short answer: Reduce each product mod 25; reduce exponent mod $\varphi (25)=20$ ⟹ $3^{36}\equiv 3^{16}\equiv 21$.
• Why: Coprimality ➔ exponent reduction valid since $\gcd (3,25)=1$.