Fast Exponentiation Algorithm

Fast Exponentiation Algorithm

The fast exponentiation algorithm is an efficient method for computing large integer powers, particularly suitable for modular exponentiation (e.g., calculating \(a^b \mod m\)). Its core idea is to reduce the exponent by binary splitting, optimizing the time complexity from the naive \(O(b)\) to \(O(\log b)\).

Problem Description

Calculate \(a^b\), where \(a\) and \(b\) are both non-negative integers (typically \(b\) is very large, e.g., \(b \geq 10^9\)). Directly performing \(b\) multiplications is too time-consuming. Fast exponentiation utilizes the binary decomposition of the exponent to reduce the number of calculations to a logarithmic level.

Solution Process

Step 1: Understanding Binary Decomposition of the Exponent

Any positive integer \(b\) can be represented in binary form. For example, the binary of \(b = 13\) is \(1101_2\), i.e.:

\[13 = 1 \cdot 2^3 + 1 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 \]

Thus:

\[a^{13} = a^{8} \cdot a^{4} \cdot a^{1} \]

Note: Terms corresponding to binary digits of 0 (e.g., \(a^{2}\)) are skipped.

Step 2: Iterative Calculation Idea

  1. Initialization: Let result \(res = 1\), base \(base = a\), exponent \(n = b\).
  2. Loop (while \(n > 0\)):
    • If the current least significant bit of \(n\) is 1 (i.e., \(n \mod 2 = 1\)), multiply \(res\) by the current \(base\).
    • Update \(base = base \times base\) (equivalent to calculating \(a^{2^k}\)).
    • Right-shift \(n\) by one bit (i.e., \(n = n // 2\)), equivalent to processing the next binary digit.
  3. Termination: When \(n = 0\), \(res\) is \(a^b\).

Step 3: Example Demonstration (Calculating \(3^{13}\))

  • Initial: \(res = 1, base = 3, n = 13\) (binary 1101)
  • Round 1 (\(n = 13\)):
    • LSB of \(n\) is 1: \(res = 1 \times 3 = 3\)
    • Update \(base = 3 \times 3 = 9\)
    • Right shift \(n = 13 // 2 = 6\) (binary 110)
  • Round 2 (\(n = 6\)):
    • LSB is 0: \(res\) unchanged (still 3)
    • Update \(base = 9 \times 9 = 81\)
    • Right shift \(n = 6 // 2 = 3\) (binary 11)
  • Round 3 (\(n = 3\)):
    • LSB is 1: \(res = 3 \times 81 = 243\)
    • Update \(base = 81 \times 81 = 6561\)
    • Right shift \(n = 3 // 2 = 1\) (binary 1)
  • Round 4 (\(n = 1\)):
    • LSB is 1: \(res = 243 \times 6561 = 1594323\)
    • Update \(base = 6561^2\)
    • Right shift \(n = 0\), end.
  • Result: \(3^{13} = 1594323\).

Step 4: Incorporating Modulo Operation (Calculating \(a^b \mod m\))

Modular exponentiation is often required in cryptographic algorithms (e.g., RSA). Simply take the modulo after each multiplication step:

  • Modify update rules:
    • \(res = (res \times base) \mod m\)
    • \(base = (base \times base) \mod m\)

Example: Calculate \(3^{13} \mod 1000\)

  • Round 1: \(res = 3, base = 9\)
  • Round 2: \(res = 3, base = 81\)
  • Round 3: \(res = (3 \times 81) \mod 1000 = 243, base = 6561 \mod 1000 = 561\)
  • Round 4: \(res = (243 \times 561) \mod 1000 = 136323 \mod 1000 = 323\)
    Result: \(3^{13} \mod 1000 = 323\).

Key Points Summary

  • Time Complexity: \(O(\log b)\), because the exponent \(n\) is halved each loop.
  • Applicable Scenarios: Large number exponentiation, modular exponentiation (number theory, cryptography).
  • Extension: Can be implemented recursively (divide-and-conquer idea: \(a^b = a^{b/2} \times a^{b/2}\)), but the iterative version saves stack space.