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,b,m):
   product = 1;
   for i=1 to b:
   product = product * a;
product = product % m;
   print(product);

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

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

Time complexity = O(log b)
in each iteration value of b getting half.

it is a Logarithmic time not polynomial-time algorithm.