##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######
(Binary exponentiation)
To compute a^n mod m: Start with result = 1. While n > 0, check if n is odd. If so, multiply result by a and take mod. Then square a and take mod. Divide n by 2.
Pseudocode: result = 1; base = a % m; while n > 0: if n % 2 == 1: result = (result × base) % m; base = (base × base) % m; n = n / 2. Return result.
This runs in O(log n) time and handles huge exponents.
