**This is an old revision of the document!**

# Homework Assignment #4

## Objective

To solve an RSA encryption problem. Also to determine asymptotic bounds on running time using the Master Theorem.

## Exercises

Show all work. i.e., justify your answers.

### Question 1

Problem 1.27 in the textbook.

Use the Extended Euclid algorithm to find the secret key $d$. Be sure to decrypt your message also to verify that everything is working.

### Question 2

In the textbook: exercise 2.1 (Karatsuba divide and conquer multiplication).

You may use the threshhold value of 2. i.e., stop recursing when the arguments to multiple are both two-bit numbers.

Tip: to make running the Karatsuba divide and conquer multiplication algorithm more straightforward, you may 0-pad (on the left) the function's arguments so that both arguments are always of even length.

### Questions 3-7

Exercises 2.5(a-e) in the textbook: find asymptotic bounds using only the Master Theorem – Big-O is sufficient.

Back to top