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

Answer:

Solution of the Brute-force

compute(b,n,mul):

  pro = 1;      //set variable for product

  for i=1 to n:

  pro = pro * b;

pro = pro % mul;

  print(pro);

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

Efficient solution

compute(a,n,m):

  pro = 1;

  a = a % m;

  while (n > 0)

  {

// If b is odd, multiply a with product

if (n is odd)

pro = (pro*a) % m;

 

n = n/2 ;

a = (a*a) % m;    

  }

  print(pro);

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

Each of the iterations of the while Loop has the value of "n" is getting half.

Therefore, the while loop runs, 2^k = n

k = log n

Explanation:

Firstly, we set a method "compute()" and take the argument "b", "n", and "mul".

Than we set the variable "pro" for the product to 1.

Than set for loop which is starting from 1 to "n".

Than we apply multiply whose product is stored in variable "pro".

Than we apply modulation of two variable and it change the value of variable "pro".

And, than print the variable "pro".

Than again we apply code according to the Time complexity.