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.

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.

cs-312/hw4.txt · Last modified: 2015/01/16 13:15 by ringger
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0