Computer-Networks
September 12, 2024Computer-Networks
September 12, 2024Computer-Networks
| Question 76 |
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 76 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)
Correct Answer: A
Question 76 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)
Subscribe
Login
0 Comments