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.

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.

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

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.

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

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.