CSci 4554 Lab 3: finding large primes

Due Tuesday, April 4 at 11:59pm (by e-mail)

30 points total

Overview and background

This lab is done in groups of 2 or individually.

The purpose of the lab is to explore probabilities and computational costs of finding large primes. You are to implement both the Fermat primality test and the Miller-Rabin test (see below for details). You will be using it with very large numbers, so use BigInteger class if you are using Java. You may use any programming language, and some have a more seamless implementation of large numbers than Java. However, below I assume Java BigInteger in the instructions.

Your goal is to explore the differences between the two primality tests, and find out how many computations you need to find two large random numbers for different bit lengths.

You will be working with integers of bit lengths 512 and 1024.

Implementing and testing primality tests

Your tasks is to implement the two primality tests with counters for the number of tests you have performed. Make sure you Specifically you need to:

Comparing the two primality tests

Try both primality tests on the following number: 9746347772161. Explain your results.

Finding large primes

Use the Miller-Rabin test to generate two primes of the bit length 512 and two of the bit length 1024. Do not use the prime number constructor. Record the number of random candidates you tried, the number of candidates a for each random candidate, and the average number of operations per candidate a.

Write down your conclusions from comparing these two bit lengths.

What to submit (by e-mail to me, CC your partner)

  1. All your program code (well-documented) and instructions for running it.
  2. All your test cases, results, counters of operations, and the number of candidates you have tried.
  3. The two large primes of bit length 512 and the two of length 1024 that you have generated.

CSci 4554 course web site.

The views and opinions expressed in this page are strictly those of the page author. The contents of this page have not been reviewed or approved by the University of Minnesota.