### 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).
• 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
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