Question

( i need Unique answer, don't copy and paste, please)

Let N be an n-bit positive integer, and let a, b, c, and k be positive integers less than N. Assume that the multiplicative inverse (mod N) of a is a^(k-1) Give an O(n^3) algorithm for computing a^(b^c) mod N (i.e., a raised to the power b^c with the result taken mod N). Any solution that requires computing b^c is so inefficient that it will receive no credit.

Answer 1

"Assume that the multiplicative inverse (mod N) of a is a^(k-1) ​​​​​​"

This can be given mathematically as:

---(1)

Assume , where is the remainder obtained when is divided by .

But from (1) we have

Where

We can calculate using modular exponentiation using the following function:

We use the following properties to solve the function:

• When is even,
• When c is odd,  
• Recursively calculate till either c = 1 or c = 0

It's important to note here that (c/2) here denotes the integral division. For example (17/2) = 8 and not 8.5.

Once we obtain , we can use the same function as described above to calculate . Replace b with a, c with r and k with N in the above function.

Complexity analysis:

In the function, at each recursive step, c is divided by 2. So the recursion depth is (since c is given to be positive integer less than N, which is a n-bit integer). And at each recursion step, we perform a multiplication. The worst case complexity of multiplication of two n bit numbers is (average case being ). So complexity of the calculate function is:

Where represents the number of bits.

We use the function two times, so overall complexity is .