Ask 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.

+4
Answers (1)
  1. 11 August, 09:22
    0
    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.
Know the Answer?
Not Sure About the Answer?
Find an answer to your 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 ...” in 📗 Computers & Technology if the answers seem to be not correct or there’s no answer. Try a smart search to find answers to similar questions.
Search for Other Answers