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?
A | O(log n) |
B | O(√n) |
C | O(n/log n) |
D | 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)
Access subject wise (1000+) question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content
Register Now
You have completed
questions
question
Your score is
Correct
Wrong
Partial-Credit
You have not finished your quiz. If you leave this page, your progress will be lost.
Correct Answer
You Selected
Not Attempted
Final Score on Quiz
Attempted Questions Correct
Attempted Questions Wrong
Questions Not Attempted
Total Questions on Quiz
Question Details
Results
Date
Score
Hint
Time allowed
minutes
seconds
Time used
Answer Choice(s) Selected
Question Text
Need more practice!
Keep trying!
Not bad!
Good work!
Perfect!