Large Prime programming assignment 3

Programming Assignment 3

Due date Wednesday 23rd September 1999, 10:00-13:00 at Lab floor 18

Large Prime

You are asked to find the large prime. It is not difficult to get one. Generate it yourself is not difficult if you have routines that handle big number (say 1000 bits ). The lecture tells you how to generate a prime (read sec. 33.8 p.837 in CLR or read Brassard and Bradley). There are information on the web that tell you about prime numbers. There are even the ready to use program to find prime. However, the challenge is this. You have to prove to me that your (large) number is really a prime. You can do that by Primality testing. That is what you have to do.

The reward will be given according to the largeness of your number. All submissions will be ranked by size. You will be given a fixed amount of time to demonstrate that your number is prime. Of course you have to run your program on the machine from Lab 18. You can use any machine reachable from the terminal in that room.

I forbid any submission that is less than 19 digits. This is to prevent a trivial submission such as 17.

Submission of the solution required the following :

On screen test that your submitted number is really a prime. You will have 5 minutes to do that.
I will give you one large number, you will have to test if that number is prime or composite. (the number is in a file as a string of digits, its size is less than 50 digits)
A written report that include the listing of the important part of your program and your analysis of the running time of your algorithm.
Answer the question how your algorithm work.