Homework Assignment #4

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

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

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.

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.

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