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.

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.

a variable of array type holds a reference of object

array are commonly used in computer program to organize data so that a related set of values

array are using zero base indexing it start with 0.

all component of array have same type, two different types doesn't use in single array

if array are store 10 quantities its index value varies from 0 to 9.

it stores 1st quantity value in index value 0 and this process will same till index value 9.

i prefer xbox one. : )