Fast Exponentiation Algorithm (Modular Exponentiation by Squaring)

Problem Description
The fast exponentiation algorithm is an efficient method for computing large power operations, especially when the exponent is very large (e.g., computing a^n, where n is a very large integer). The conventional iterative multiplication approach has a time complexity of O(n), while the fast exponentiation algorithm can optimize it to O(log n). This algorithm is widely used in cryptography, large number arithmetic, and other scenarios.

Solution Approach
The core idea of the fast exponentiation algorithm is divide and conquer and binary representation. It utilizes the binary representation of the exponent, decomposing the exponent n into a sum of powers of 2, thereby transforming the computation of a^n into calculating the product of a series of squared powers of a.

Detailed Steps

1. Convert the exponent n to binary form
   This is the foundation for understanding the algorithm. For example, to compute 3^13.
   The binary representation of exponent 13 is 1101.
   13 = 1 * 2³ + 1 * 2² + 0 * 2¹ + 1 * 2⁰ = 8 + 4 + 0 + 1

2. Decompose the power expression
   According to the laws of exponents, a^(m+n) = a^m * a^n.
   Therefore, 3^13 = 3^(8+4+1) = 3^8 * 3^4 * 3^1
   Note that we skip the terms corresponding to binary digits of 0 (3^2, because the second binary digit is 0).

3. Iterative Process of the Algorithm
   We don't need to pre-calculate all 3^(2^k). Instead, we can compute iteratively, starting from the least significant bit (or most significant bit).

   Method 1: From LSB to MSB (More Common)
   We maintain two variables:

   • base: Represents the weight of the current bit, i.e., a^(2^k). During iteration, base is continuously squared.
   • result: Stores the final result. When a binary digit of the exponent n is 1, we multiply the current base into result.

   Steps for computing 3^13:
   Initialization: result = 1, base = 3, n = 13

   Step	n (binary)	Current Bit (n % 2)	Description	result update	base update (for next step)	n update
   Init	1101	-	-	1	3	13
   1	1101	1 (LSB)	Current bit is 1, multiply base (3^1) into result	result = 1 * 3 = 3	base = 3 * 3 = 9 (i.e., 3^2)	n // 2 = 6
   2	110	0	Current bit is 0, do not multiply into result	result remains 3	base = 9 * 9 = 81 (i.e., 3^4)	n // 2 = 3
   3	11	1	Current bit is 1, multiply base (3^4) into result	result = 3 * 81 = 243	base = 81 * 81 = 6561 (i.e., 3^8)	n // 2 = 1
   4	1	1	Current bit is 1, multiply base (3^8) into result	result = 243 * 6561 = 1594323	-	n // 2 = 0
   End	0	-	n is 0, loop ends. result is the final result 1594323.	-	-	-

   Core Code (Non-Recursive Version)

   def fast_power(a, n):
       result = 1
       base = a
       # Continue loop while exponent n is greater than 0
       while n:
           # If the current binary digit of n is 1
           if n & 1: # Equivalent to n % 2 == 1
               result *= base
           # Square base for the next digit
           base *= base
           # Right-shift n by one bit, equivalent to n //= 2
           n //= 2 # Or use bitwise operation n >>= 1
       return result
   

4. Handling Modulo Cases
   In practical problems (e.g., calculating Fibonacci numbers, RSA encryption), it's often necessary to compute the result modulo a large number (a^n % mod). The fast exponentiation algorithm can easily incorporate modulo operations because modulo distributes over multiplication: (a * b) % mod = ((a % mod) * (b % mod)) % mod.

   Fast Exponentiation Code with Modulo

   def fast_power_mod(a, n, mod):
       result = 1
       base = a % mod # Take modulo first to prevent initial a from being too large
       while n:
           if n & 1:
               result = (result * base) % mod
           base = (base * base) % mod
           n //= 2
       return result
   

Summary
The essence of the fast exponentiation algorithm lies in using the binary representation of the exponent to optimize from O(n) multiplications to O(log n). The steps can be summarized as:

1. Initialize the result result to 1 and the base base to a.
2. Loop until the exponent n becomes 0:
   • Check if the least significant bit of n is 1 (n & 1), if yes, multiply the current base into result.
   • Square base.
   • Right-shift n by one bit (divide by 2).
3. Return result.

This method significantly improves the efficiency of large number exponentiation.