Chat with us, powered by LiveChat Data Structures and Algorithms 22:544:613:SEC03 & 26:198:685SEC03 Homework 3 Instructor: Farid | Max paper

Data Structures and Algorithms

22:544:613:SEC03 & 26:198:685SEC03

Homework 3

Instructor: Farid Alizadeh
Due Date: Sunday November 21, 2021, at 11:50PM

last updated on November 8, 2021

Please answer the following questions in electronic form and upload and
submit your files to the Canvas Assignment site before the due date. Make sure
to click on the submit button.

You have two choices for the format.

First Choice: Submit in pdf format all theoretical questions. You may ei-
ther typeset or hand-write your answers. In case of hand-write transform your
work into pdf using apps such as CamScan. You should have only a single
pdf file. For Python scripts, include the text of the script as a separate *.py
file. You should have a single file for Questions 3 & 4. For other questions, if
you use Python to compute your answers include it with the pdf text above.

Second Choice: You can use a single Python Notebook *.ipynb file. You
should use the text format of the notebook for the theoretical results, and the
Python script for the programming parts.


22:544:613SEC03 & 26:711:685SEC03, Fall 2021
Homework 3 Due date: 11/21/2021 at 11:50PM

1. Solve the following recurrence relations and give the solution in terms of
Θ(·). Explain if the master method is applicable. If so, use the master
method. If not, directly solve the recurrence.

1a) F(n) = 3F(n/4) + log(n)

1b) F(n) = 4F(n/2) + n3

1c) F(n) = F(n/2) + 1

1d) F(n) = 2F(n/2) + n log(n)

2. In the this question by using a sequence of algebraic manipulations we
develop an algorithm that computes the coefficients of p(t + α) for some
constant α, given the array of coefficients of p(t). Suppose p(t) = p0 +
p1t + · · · + pntn is a polynomial of degree n.
Observe that the coefficients of (t+α)k are given by binomial coefficients(

= k!


(t + α)k =



αk +



tαk−1 +



t2αt−2 · · · +









Another, equivalent definition of binomial coefficients is given by the re-
currence relation: (






= 1(




k − 1

j − 1



j − 1

This quantity, in particular, also counts the number of subset of size j of
a set of k elements.

2a) Devise an algorithm that for an integer k, all numbers

for i, j ≤ k

are calculated. What is the complexity of this algorithm? (Look up
Pascal Triangle) If we only want for a fixed k the numbers




22:544:613SEC03 & 26:711:685SEC03, Fall 2021
Homework 3 Due date: 11/21/2021 at 11:50PM

j = 0, . . . ,k, using the factorial formula above, what algorithm should
we use and what is its time complexity?

2b) Now consider the polynomial p(t) = p0 + p1t + · · · + pntn. We
wish to compute the coefficients of the shifted polynomial p(t + α) =
q0 + q1t + · · · + qntn, where α is a fixed number. Explain how you
can use the Fast Fourier Transform to compute qi from pi and α. In
total what is the time complexity of recovering coefficients of p(t+α)
from the coefficients of p(t)? (Hint: Expand each term of the shifted
polynomial, and collect terms for each power ti, and try to see if you
can detect a convolution.)

3. Here is a modification to Euclid’s algorithm which does not use division
or mod operations. It only uses subtraction and division by two, which in
computers, where numbers are represented in binary form, only involves a
simple shift. For instance, 100110/2=010011 and 100111/2=010011 with
a remainder of 1.

3a) Show that if a and b are both even numbers, then gcd(a,b) = 2 gcd(a/2,b/2)

3b) Show that if one of a and b is even and the other odd, say a is even
and b is odd, then gcd(a,b) = gcd(a/2,b).

3c) If both a and b are odd then show that gcd(a,b) = gcd

3d) Use the above facts to design an algorithm for finding gcd where only

subtraction, division by two and checking if an integer is even or
odd. Present your algorithm in a precise pseudocode (If you wish you
can instead use Python instead of pseudocode, but this is voluntary.)
Provide a time complexity analysis of your algorithm.

4. While the exponentiation operation k = ab mod c can be computed in
polynomial time and can be efficiently implemented, the inverse operation
is quite difficult to achieve. More precisely, given c, k and a, no one
knows an efficient algorithm to find b. The number b in the relation
k = ab mod c is called the discrete logarithm of k in base a and mod c.
It is conjectured that no efficient algorithm exists in general to compute
the discrete logarithm b for any given values of k,a and c1.

1A computer scientist, Peter Shor, however, has devised a polynomial-time algorithm for
both discrete logarithm and for integer factorization using quantum computers.


22:544:613SEC03 & 26:711:685SEC03, Fall 2021
Homework 3 Due date: 11/21/2021 at 11:50PM

The Diffie-Hellman public key exchange is a protocol where two parties
exchange a secret shared key over the open channels (for instance, the in-
ternet) and can use this shared key to send each other encrypted messages
that only they can decrypt. See the wikipedia page for more informa-
tion. The strength of the method rests on the assumption that computing
discrete logarithm mod very large prime numbers is computationally in-

Here is how two people, Alice and Bob, who don’t even need to know
each other, and are only aware of each others’ e-mail or IP addresses
can exchange a shared key, K which only the two of them will know.
Assume a third party, Eve, is eavesdropping, but otherwise can not alter
the messages. The protocol works as follows. The teal-colored items are
public and anybody eavesdropping can know them. The orange-colored
items are secret and known to only the owner.

• Alice selects a large prime number p and another number g. She also
chooses a private key a which only she knows and computes A = ga

mod p. Alice sends A,p and g to Bob.

• Bob, upon receiving Alice’s A,g and p, chooses a private key b which
only he knows. He computes B = gb mod p and sends it back to
Alice. Note that by this stage everyone, including Eve, know the
values of p,g,B,A.

• Alice computes K = Ba = gab mod p.
• Likewise, Bob computes Ab = gba mod p = K.

So now both Alice and Bob are in possession of the shared key K that
nobody else knows. They can use this key to send each other messages.
For instance, they can use the XOR method. If Alice wishes to send Bob
the message M, she computes E = M ⊕ K (the result of applying XOR
to the binary representations of M and K,) and sends it over the open
channel to Bob. Once Bob receives E, he decrypts it by M = E ⊕ K.
Note that Eve, knowing A,B,g, and p, as well as the encrypted message E,
nevertheless cannot find out what K is easily. To do so she needs to solve
the equation gx = A mod p, to find a = x, and solve gy = B mod p
for y = b. If she could do so, then she would know K = gab mod p and
would be able to decrypt E and recover the message M = E ⊕ K.

4a) Write in Python a class called diffHellSend for the person who ini-
tiates a communication (Alice). The init method of this class
should have three optional parameters: a the sender’s secret key a
defaulted to None, and a pair of integers low (default 0) and high


22:544:613SEC03 & 26:711:685SEC03, Fall 2021
Homework 3 Due date: 11/21/2021 at 11:50PM

(default 2100) which will be the range of random integers to be cho-
sen later2. Furthermore, the init method should set the values of
a,g,p, and A. For generating p you may use the methods provided
in the number theory and cryptography module. If the argument a is
None its value should be randomly generated. The other values that
are not computed by a formula should also be randomly generated.

All of these values should be private attributes. The class should have
a method called getPublic which returns the public values, that is
A,g and p.

In addition, this class should have a method called receive which
receives the value of B from the other person (Bob). Using B it should
compute the common key K, which should be another private member
of the class.

Finally, the class should have a method crypt which should take a
message M and encrypt it using the XOR operation with key K and
return E, the encrypted version of M.

4b) Write a second class for the second person (Bob) who is signaled to
have a communication with the first person; this class should be called
diffHellReceive. The init method of this class should take the
public values of A,g,p, and possibly Bob’s secret key b (which has
the default value of None.) It should also have the optional arguments
low (defaulted to 0) and high (defaulted to 2100.) If b equals None
a random integer between low and high should be used for it. Also
init should compute the value of B and the common secret key
K, both of which should be private members of the class.

The class should have the method getPublic which returns the public
value B.

The class should also have a method called crypt that takes a secret
message E from the sender Alice and decrypts is using XOR and the
secret common key K and returns Alice’s original message M.

4c) Create a diffHellSend object called alice and set her secret key
a = 700090980808 (let low and high be the default values.)

4d) Create a diffHellReceive object bob and set his secret key b =
209573994589 (let low and high be the default values.)

4e) Alice wishes to send the message “M=159786939486074610063241937”
to Bob. Write the sequence of calls necessary to send the message,

2Use Python module random and the method randint(low,high) to generate arbitrary
long random integers


22:544:613SEC03 & 26:711:685SEC03, Fall 2021
Homework 3 Due date: 11/21/2021 at 11:50PM

and for Bob to receive and decrypt the message. Print, M, E Alice’s
encrypted message and Bob’s decryption M1 and see if M = M1.

5. Alice and Bob are participating in an online community that uses the RSA
public key system for secure communications.

5a) For Alice compute random prime numbers pa, and qa between 2
50 ≤

pa,qa ≤ 252. Similarly, for Bob compute random prime numbers pb,
qb between 2

50 ≤ pb,qb ≤ 252.

5b) Compute na and the Euler function φ(na), and nb and φ(nb).

5c) Alice chooses `a = 73 for her public key in an RSA system. Compute
her private key ka. Similarly, Bob chooses `b = 41 for his public
key. Compute his private key kb. Write a function called find k to
compute ka from `a and , kb, from `b.

5d) Write a Python function crypt that takes a list of integers as the
message and encrypts them one by one, using a provided pair of keys.
The pair may be either the receiver’s public key (`,n), or it could be
the sender’s private key (k,n). The function should return the list of
encrypted integers as computed by the RSA system.

5e) Write a function txtToRSA which takes a string and a pair of inte-
gers (k,n). This function first turns the string into its list of unicode
integers, and encrypts this list (by using crypt function above) and
outputs the encrypted list of integers. You may use the built-in func-
tion ord(c) to turn each character into its unicode equivalent.

5f) Write a function RSAtoTxt which takes a list of integers, and a pair of
additional integers (`,n) and using crypt decrypts the list to recover
the unicode integers. It then turns the unicode integers into a single
string. You may use the built-in function chr(m) that takes an integer
m and returns its unicode equivalent character (so ord and chr are
inverse of each other.)

5g) Write a function RSAsign that takes a text message M from the sender
(say Bob) and a signature from him with exactly ten characters, and
computes the RSA encoding along with the signature. Note that you
need to do two encryptions: First, encrypt the message M using Bob’s
private key kb to get Eb. Then attach Bob’s signature (text turned
into a list of ten integers σb) using the built-in function ord and form


22:544:613SEC03 & 26:711:685SEC03, Fall 2021
Homework 3 Due date: 11/21/2021 at 11:50PM

Eb + σb (’+’ here refers to appending of two lists of integers.) Then
encrypt this joined list again, this time using the receiver’s (say Alice)
public key `a.

5h) Next write a script unpack that gets the message from sender (Bob),
and then uses receiver’s (Alice) own private key to decrypt it and re-
cover Bob’s signature σb and his encrypted message Eb. Note, since
Alice knows Bob’s signatire is exactly ten characters, she can take the
last ten numbers of the decrypted list, and turn them into characters
by using the built-in chr function. Then she takes away Bob’s sig-
nature from the end of the once decrypted list and then uses Bob’s
public key to decrypt the rest of the encrypted message to get Bob’s

5i) To test your code, suppose Bob wants to send the message “Bitcoin
to double next week! ” Also, let’s Bob’s signature be simply “Bob”
followed by enough blank characters to make it exactly ten characters.
Print, pa,qa,na,φ(na) for Alice and similarly, pb,qb,nb,φ(nb) for
Bob. Set public keys `a = 73 and `b = 41. Find and print Alice and
Bob’s private keys.

Print the encrypted message Alice receives. Print Alice’s completely
decrypted message and recover Bob’s message to Alice along with
Bob’s recoverd message and check to see they are what Bob sent.


error: Content is protected !!