COMP 4109: Assignment #4

Assignment #4 was distributed on March 3th, 2005. It is due on March 14th at 2:30 PM in class. Please email program code and outputs to Mohammad Mannan (mannan at, packaged as a zip file with the name "<your name>-<your student ID>". Be sure to turn in all new code that you have written to answer these questions.

Partial solutions for Assignment #4


  1. Question 1f (the PSS signature problem) is now extra credit, worth 25% of one assignment.
  2. For parts b,d, and e of Question 2, assume that we want to choose t in terms of P(Miller-Rabin(x)=prime|x is composite). This basic bound is given by Fact 4.25 (p.140). The question as written actually refers to P(x is composite|M-R says prime), which is much more difficult to calculate. If you successfully solve these parts as written, it is worth extra credit of 25% of one assignment (no partial extra credit).

Here is the information you will need to complete the assignment:

Remember to show your work for all problems. For 1a (RSA key generation), this means that you will need to implement the extended Euclidean algorithm in a way that supports big integers. (Running this algorithm by hand would be very difficult.) Rather than doing this in C, I suggest that you do your work in a higher-level language such as Perl or Java. Here is an example Perl program that shows how to perform basic operations with big integers. For more documentation, look up Math::BigInt. On the other hand, If you prefer to program in C, I would suggest that you use the GNU multiprecision library (gmp) rather than implement your own big integer package.

One other tip: when the assignment says "manually," that means that you must show the appropriate intermediate computations. While you may write a program to help accomplish the task, you will need to walk through the process step-by-step and show your work.

Good luck!

Created by soma at
Last modified: March 3, 2005.