edited by
7,257 views
35 votes
35 votes

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 _______.

edited by

7 Answers

3 votes
3 votes

this is the algorithm to find  amod n.

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

hence 211 mod 8 = 0

3 votes
3 votes

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$.

Answer:

Related questions

62 votes
62 votes
12 answers
1
go_editor asked Feb 12, 2015
20,901 views
Consider the following C function.int fun(int n) { int x=1, k; if (n==1) return x; for (k=1; k<n; ++k) x = x + fun(k) * fun (n-k); return x; }The return value of $fun(5)$...
44 votes
44 votes
5 answers
2
go_editor asked Feb 15, 2015
10,734 views
Let $G$ be a connected undirected graph of $100$ vertices and $300$ edges. The weight of a minimum spanning tree of $G$ is $500$. When the weight of each edge of $G$ is i...