GATE CSE 2015 Set 3 | Question: 49

Question

Suppose $c = \langle c[0], \dots, c[k-1]\rangle$ is an array of length $k$, where all the entries are from the set $\{0, 1\}$. For any positive integers $a \text{ and } n$, consider the following pseudocode.

DOSOMETHING (c, a, n)

$z \leftarrow 1$
for $i \leftarrow 0 \text{ to } k-1$
     do $z \leftarrow z^2 \text{ mod } n$
     if $c[i]=1$
           then $z \leftarrow (z \times a) \text{ mod } n$
return z

If $k=4, c = \langle 1, 0, 1, 1 \rangle , a = 2, \text{ and } n=8$, then the output of DOSOMETHING(c, a, n) is _______.

Comments

Is there some misprint? As there's no indentation between do and if. So we should consider them separately right? Then do loop won't end. So for question like this if a person challenges would it be considered?

---

 

In question, 

  do z←(z^2) mod n

it is normal statement equivalent to,

              z=(z^2) mod n  

Am i correct or it is do while loop… like above comment saying.

---

There needs to be a “while” for a do-while loop, or at least a condition.

This form of pseudocode notation → generally means assignment operator, unless and until specified.

You are correct.

Answer 1

May be this works ...........

Answer 2

this is the algorithm to find  a^c mod n.

here a =2, c =(1011)₂ = 11, n=8

hence 2¹¹ mod 8 = 0

Comments

How can u assume this thing ?

---

Any Proof ? Which Text Book It From ? @y mint

Answer 3

Initial value $z=1$.

Let's check the values of the binary array $c=[1,0,1,1]$.
When $c[0]=1$ it is $z \leftarrow z^2 = 1$ and $z \leftarrow z\times a = 1\times a =a$

When $c[1]=0$ it is $z \leftarrow z^2 = a^2$ and $z \leftarrow z\times a$ is not evaluated.

When $c[2]=1$ it is $z \leftarrow z^2 = (a^2)^2=a^4$ and $z \leftarrow z\times a = a^4\times a =a^5$

When $c[3]=1$ it is $z \leftarrow z^2 = (a^5)^2=a^{10}$ and $z \leftarrow z\times a = a^{10}\times a =a^{11}$

 

Note that $(1011)_2=11$ from the binary array $c=[1,0,1,1]$.

So the question reduces to $a^{\text{DecimalValue(Binary Array }c)}\mathrm{~mod~}n$

$\therefore a^{11} \mathrm{~mod~}n = 2^{11}\mathrm{~mod~}8=0$

So the output is $0$.