0
Question 1 |
Exponentiation is a heavily used operation in public key cryptography. Which of the following options is the tightest upper bound on the number of multiplications required to compute bn mod m, 0≤b, n≤m?
O(log n) | |
O(√n) | |
O(n/log n) | |
O(n) |
Question 1 Explanation:
In this we need to compute like
C1 = bn/2 × bn/2
C2 = bn/4 × bn/4
C3 = bn/8 × bn/8
⋮
Ck = b2 × b2
Recurrence relation T(n) = T(n/2) + O(1)
T(n) = O(log n)
C1 = bn/2 × bn/2
C2 = bn/4 × bn/4
C3 = bn/8 × bn/8
⋮
Ck = b2 × b2
Recurrence relation T(n) = T(n/2) + O(1)
T(n) = O(log n)
There is 1 question to complete.