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:

• Implement Fermat primality test as described in your textbook or here. Set k to some initial number. Add a counter to count the number of candidates a that you tried before you have determined that your nubmer is composite. Your number is prime if you have finished all k tests and didn't find a counterexample.
  Some really helpful methods:
  • The method modPow of BigInteger allows you to calcualte a very large power of a very large number modulo another large number efficiently: it reduces all intermediate results modulo a given N.
  • A BigInteger constructor that allows you to generate a random BigInteger of a given bit length.
  • A BigInteger constructor that generates a random prime integer. You can use it for testing your primality tests, but not for the last task of your lab (fidning the large primes).
• Test your method on numbers that you know to be prime (obtained from the prime number constructor) and on numbers that you know to be composite, such as a product of two large primes, each half the length and a number that has a lot of small prime factors. You need to test it for both the length 512 and 1024 bits (approximately). Record the counters for all your test cases. Adjust k if needed.
• Implement Miller-Rabin test as described in the book or here.
• Test it on a few numbers of bit length 512 and 1024 that you know to be prime (i.e. generated by the prime numbers constructor) or you know to be composite (i.e. generated as a product of two smaller primes). Adjust the number of candidates a you try. Record the number of candidates and operations per candidate.

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.