HW#4 --- last modified April 21 2019 00:11:41.

Solution set.

Due date: Apr 24

Files to be submitted:
  Hw4.zip

Purpose: To gain experience with online and number theoretic algorithms.

Related Course Outcomes:

The main course outcomes covered by this assignment are:

LO6 -- Analyze or code a number theoretic algorithm

Specification:

This homework will consist of two parts, a written part and a coding part. Both parts will be submitted in the Hw4.zip file. The written part should be in a file Hw4.pdf. For the written part of the homework you should write solutions for the following questions. In what you turn in, make sure to write the names and student ids for each group member. For each problem, first copy and paste the question, then write your solution to it beneath it.

1. Let `k=5`. Assume a cache with initial contents 1,2,3,4,5 and with at least one item not in the cache. Give an example sequence of length at least 6 of cache requests and a sequence of random choices by the Marker algorithm so that its competitiveness on this sequence with these choices would be greater than `H_5`.
2. Use the extended Euclidean algorithm to find the multiplicative inverse of `26 mod 1155`. Solve `9x equiv 6 mod 33` for all solutions.
3. Using the Chinese Remainder theorem, determine a number `x mod 1155` that satisfies `x equiv 2 mod 3`, `x equiv 3 mod5`, and `x equiv 4mod 7`, and `x equiv 5 mod 11`.
4. Suppose `p=7`, `q=17`. If we choose `e=5`, what would be a the RSA public and private keys? Show the result of encrypting with the private key, the message `89`. Show the steps in decrypting it, to get the original number back.

For the coding part of the homework, I want you to code either a Java or Python implementation of a prime number finder. Your prime number finder should make use of the Miller Rabin algorithm. I will run your program from the command line using the format:

java PrimeFinder length num_trials

or

python PrimeFinder.py length_num num_trials

For example,

java PrimeFinder 3 7

On a given input PrimeFinder should find the least number that passes num_trials many Miller Rabin trials of length between length_num and length_num +1 and output it in binary. On the particular example above, the output should be:

101

By Sylvester's Theorem, we know there is always a prime in this range. For 0.5pts of your coding points described below, plot `log_2(x-2^{n-1})` vs `n` where `x` is your output for values `n` between 100 and 200. Say what you observe.

Point Breakdown