Exponentiation is a heavily used operation in public key cryptography. Which…
2007
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(logn)
- B.
O(√n)
- C.
O(n/logn)
- D.
O(n)
Attempted by 99 students.
Show answer & explanation
Correct answer: A
Answer: O(log n)
Key idea: Use exponentiation by repeated squaring (binary exponentiation).
Write the exponent n in binary and let L = floor(log2 n) + 1 be the number of bits.
Compute powers by repeated squaring: for each of the remaining L-1 bits you perform a squaring (at most L-1 squarings).
Whenever a processed bit equals 1, multiply the running result by the current power. The number of such multiplications is at most L-1.
Total multiplications ≤ (L-1) squarings + (L-1) multiplications ≤ 2L − 2 = O(log n).
Therefore the tightest upper bound on the number of multiplications required to compute b^n mod m is O(log n).