Modular Exponentiation (or) Fast Multiplication

Things we will be discussing here.
  • Modular Exponentiation
Modular Exponentiation
  • Useful to compute (An)%M when both A and ‘n’ are large i.e in range of 10e18
  • The basic approach in finding ( An )%M
    • First, find (An) as Result = A*A*A*...*A , ‘n’ number of times
    • Then take the Result%M.
    • The running time of this algorithm is O(n).
    • Disadvantage:
      • Leads to Integer Overflow => wrong answer in Computer System for Large Number.
      • Very inefficient for Larger Number.

  • Optimized method:
    • We can write An = {A2}n/2 for even number ‘n’.
    • An = ({A2}n/2)*A  for odd number ‘n’.
  • Example:
    • 35 = {32}5/2 * 3 = 92 * 3
    • 210 = {22}5 => 45 = {42}2 * 4 => 162 * 4 = 256*4 => 1024
    • Now if we observe in the above example every time n is getting decreased by n/2. 
    • It can be solved Recursively.
    • Recurrence Relation:  T(n) = T(n/2) + O(1)
      • Therefor time complexity = O( logn )
Time Complexity: O( logn )

Implementation:


Practice Problems
  1. Mystery
  2. Parking lot ( 630I )
In the next article, we will be discussing GCD and LCM. If you find any error or have some advice then feel free to comment.

Thank You

Comments