GATE IT 2007 | Question: 17

Question

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 $b^n \bmod{m}, 0 \leq b, n \leq m$ ?

• A. $O(\log n)$
• B. $O(\sqrt n)$
• C. $O\Biggl (\frac{n}{\log n} \Biggr )$
• D. $O(n)$

Comments

explain

---

Same type of question https://gateoverflow.in/1469/gate1999-1-16

---

nice explained, but what if they'll ask about best time complexity ->(best case)

then i think can we follow fermat's little theorem ->

            b^n mod m   i.e.  n = m-1 and , moreover b and m are co-prime then remainder would be 1.

hence O(1). can we follow this approach for best case only ?

edit note :  we can apply conditional  if else for this specific condition that leads to O(1).

Answer 1

Correct Option: A

We need to divide $n$ recursively and compute like following:

$C_1 = b^{\frac{n}{2}} \times b^{\frac{n}{2}}$. In this, we need to calculate $b^{\frac{n}{2}}$ only once.

$C_2 = b^{\frac{n}{4}} \times b^{\frac{n}{4}}$

$\vdots$

$C_k = b^2 \times b^2 \qquad \Bigg \{k = \log n$

Recurrence relation: $T(n) =T \Bigl (\frac{n}{2} \Bigr ) + O(1)$

$T(n) = O(\log n)$

Comments

If we are not assuming that then how can we say that computation of b^n will take at Max logn multiplications, when it can actually take more??

In the question it is mentioned that we have to consider the worst case, so why we are not considering that we used iterative method??

---

@svmk_18

Where the “worst case” is mentioned in the question ?

Best Case, Worst Case, Average Case all these terms are used with an “Algorithm”. But here, no particular algorithm is given.

“Theta” is a “tight” bound and above it is already proved mathematically that number of multiplications for the computation of $b^n$ is $\Theta (\log n)$ which means upper and lower bounds are $O(\log n)$ and $\Omega(\log n)$ respectively.

Now, in question, we have given various upper bounds and we need to find the “tightest” upper bound which means which upper bound has least growth rate among them.

Mathematically, you can prove that the “tightest” upper bound is $\log n$ for sufficiently large “n”.

$\lim_{n \rightarrow \infty}\dfrac{n}{\log n} = \infty$ i.e. $n > > \log n$

$\lim_{n \rightarrow \infty}\dfrac{\sqrt{n}}{\log n} = \infty$ i.e. $\sqrt{n} > >\log n$

$\lim_{n \rightarrow \infty}\dfrac{\frac{n}{\log n}}{\log n} = \infty$  i.e. $\frac{n}{\log n}> >\log n$

---

Ok got it. Thanks. :)

Answer 2

Answer is (A)

1. First find out b^2 which will require 1 multiplication(b*b)..store the value of b^2(say in variable 'a') for further use...

2. b^4 can be find out  using a*a ie 1 multiplication, therefore total of 2 multiplication (including step 1). Store the value of b^4 in variable 'c' for further use.

3. Similarly b^8 can be calculated by c*c i.e 1 multiplication and total of 3 multiplication (including step 2)....and so on. Therefore O(log n) is the complexity for the no. of multiplications required.

Answer 3

Or You can start from $b^1$ and keep squaring  :   $ b^1 b^2 b^4 b^8 ...  b^n $

where each squaring operation is a multiplication, which is asked in the question. $= O(logn)$

Comments

@redbloodpro

can u describe ur answer i m not getting

let take  n=8 b=2 m=5

b^n mod m = 2^8 mod 5 so here we need to find 2^8 means 8 times we mutliply 2*2*2*2*2*2*2*2 so how it will me log n ?

---

from b compute $b^2$ - 1 multiplication

from $b^2$ compute $b^4$ - 1 multiplication

from $b^4$ compute $b^8$ - 1 multiplication. So total $log(8) multiplications$, you can apply mod at every step.

---

sorry i did not get u

---

@redbloodpro

what does meant by keep squaring ?

---

Operations of the form bⁿ mod m can be calculated efficiently by divide and conquer approach by splitting it into ( b^n/2 mod m * b^n/2 mod m) mod m. 

For eg : 7⁵ mod 4 can be split into ((7³ mod 4 )* (7² mod 4))mod 4. This can be done iteratively.

i.e 

b^n/2 mod m = ( b^n/4 mod m * b^n/4 mod m) mod m  so on... b^n/4 has to be calculated only once.

So this can be represented by the recurive relation. T(n) = T(n/2) + 1 . Applying masters thorem answer is O(logn)

---

can u explain with
taking a value on a , b, m it will make a clear picture .