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 ³ ) 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 rating: 100% (QA)

Assume that the multiplicative inverse mod N of a is ak1 This can be given mathematically as 1 Assum... View the full answer