HW#4 --- last modified May 04 2022 00:46:19.

Solution set.

Due date: Apr 25

Files to be submitted:
  Hw4.zip

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

Related Course Outcomes:

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=6`. Assume a cache with initial contents 2,3,4,5,6,7 and with at least one item not in the cache. Give an example sequence of length at least 7 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_6`.
2. Use the extended Euclidean algorithm to find the multiplicative inverse of `14 mod 2145`. Solve `6x equiv 9 mod 33` for all solutions.
3. Using the Chinese Remainder theorem, determine a number `x mod 2145` that satisfies `x equiv 2 mod 3`, `x equiv 3 mod5`, and `x equiv 4mod 11`, and `x equiv 5 mod 13`.
4. Suppose `p=11`, `q=17`. If we choose `e=3`, what would be a the RSA public and private keys? Show the result of encrypting with the private key, the message `83`. Show the steps in decrypting it, to get the original number back.

For the coding part of the homework, I want you to code in Java (only language allowed for this HW) 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

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

Using your program I would then like you to design and conduct some experiments concerning the density of twin primes. Here a twin prime is a pair of primes `p`,`q` such that `q = p+2`. Split the numbers in the range 1,000,000 to 2,000,000 into bins of size 10000. Use your program to count the number of twin primes in each bin and plot the result. Suggest a function that seems to fit the distribution of twin primes versus `n` that you observe. Put the write-up of your experiment also in Hw4.pdf.

Point Breakdown