# Homework Assignment #4

## Objective

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

## Exercises

### 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 Big-O bounds using only the Master Theorem.