Question

The time complexity to perform the modular exponentiation of a ≡ c^g (mod m).

(a) O(m+a)

(b) O(a*g)

(c) O(gm)

(d) O(g)

I got this question in homework.

Query is from Number Theory topic in portion Number Theory and Cryptography of Discrete Mathematics

Answer 1

The correct option is (d) O(g)

For explanation I would say: The modular exponentiation completely depends on the operating system environment and the processor for its performance. The above said method requires a time complexity of O(g) for its completion.