Chris Pollett>
CS255 |
HW#4 --- last modified May 04 2022 00:46:19.Due date: Apr 25 Files to be submitted: 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.
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
|