Question

Given the three numbers, a, n and m, compute a^n mod m. What is the input size and why? What is the brute-force solution for this problem and what is its complexity? Give the most efficient algorithm for this problem that you can, analyze its time complexity T(n), express it as a function of the input size and argue whether or not it is a polynomial-time algorithm.

Answer 1

Brute-force solution
compute(a,n,m):
   product = 1;
   for i=1 to n:
   product = product * a;
product = product % m;
   print(product);

Time complexity = O(n) Loop from 1 to n

Efficient solution
compute(a,n,m):
   product = 1;
   a = a % m;
   while (n > 0)
   {
// If b is odd, multiply a with product
if (n is odd)
product = (product*a) % m;
  
n = n/2 ;
a = (a*a) % m;   
   }
   print(product);

Time complexity T(n)= O(log n)

In Each iteration of while Loop value of n getting half.
Therefore wile loop runs for 2^k = n
k = log n