Project #1: Primality Tester

The purpose of this project is to get you up and running with Visual Studio and to familiarize you a little with the tools. You will also gain experience with algorithms for modular arithmetic. In this project, you will implement the prime number test based on Fermat's little theorem (see pseudo-code on page 27, figure 1.8 of the text book).

You are developing as a problem solver. You are also learning to solve a problem before you start writing code. In this project, we require you to step up to a whiteboard after reading these instructions before writing any code. Use the whiteboard to walk through the solution with a friend. Your friend could be another CS major, a CS 312 classmate, or another technical person with an eye for detail.

In short, make sure you understand what you are going to do before you write a stitch of code. As you will note below, including a photo of your “whiteboard experience” is a required element of your project report.

Have a “whiteboard experience” and document it with a photograph of you next to the whiteboard sketches, etc.

Prepare a whiteboard experience report as a .pdf file. It should consist of one page with the following elements:

• your name
• your section number
• [5 points] your photo
• [5 points] a caption (2-3 sentences) explaining why you are ready to proceed to write code
• the names of the people in your audience

Submit the whiteboard experience report online by the whiteboard experience deadline for this project.

1. Have a “whiteboard experience” as directed above, and submit it online by the deadline for the whiteboard experience.
2. Fire up VisualStudio 2010 and start a new windows C# project. (Project type should be set to “Visual C#” then select the “windows application” template).
3. Create a form with two textboxes and a button. (Buttons and textboxes can be selected from the toolbox in the form designer. If the toolbox is not visible, click on “View | Toolbox”).
4. Name one textbox “input” and the other “output” (right click on the textbox to view properties. One of the properties is the name. The default name will be textBox1 or something similar).
5. Name the button “solve” and change the text label to “solve” (again, right click on the button to set the properties. The text label field is called “text”).
6. Next we want to create the code that will be executed when the solve button is clicked. To do this, double-click on the solve button in the form designer. Doing so will create a stub for the method that will be called when the button is clicked. You can then type your code into that stub.
7. You should now be editing code in a method called solve_click() in a file called Form1.cs
8. Any number that's big enough to be interesting will overflow the capacity of a standard int. To deal with this, you'll need to make use of the System.Numerics.BigInteger type:
   • In the menu, go to Project → Add Reference…
   • Click on the .NET tab.
   • Scroll down to System.Numerics, select it, and hit OK.
   • Add using System.Numerics; to the top of your .cs file.
   • If System.Numerics does not appear to be present in the list of available references, bring up the properties of your project (can use the key-chord Alt+F7). For the property “Target framework:”, specify .NET Framework 4 (or higher).
9. Code up the primality test pseudocode from figure 1.8 of the textbook.
   • Neither 0 nor 1 is prime, so assume your input is greater than 1.
   • You may set k to any value you like (see p. 27 in the printed text, p. 37 in online version). E.g., k = 20 is a reasonable value.
   • Implement modular exponentiation (pseudo-code in figure 1.4). Your primality test must use your own modular exponentiation function.
10. If Fermat's test returns “yes” then write “yes with probability p” (where p is the probability that the input was prime) in the output textbox. If Fermat's test returns “no”, then write “no” in the output textbox.
11. Document your algorithm with legible comments in important places in the code that make it obvious to the reader what your solution is doing. This documentation also provides evidence of your comprehension. With the aid of adequate documentation, the correctness of your approach should be easy for the reader (e.g., TA) to verify. If the TA cannot easily determine the code's correctness, then fewer points will be awarded.

• The contents of the input text-box can be accessed as: input.Text
• A string can be converted to an integer using: BigInteger.Parse(input.Text)
• You can set the value of the text in a text-box as follows: output.Text = "the output"
• To generate a random BigInteger as a test quantity $a$, you could take the following steps:
  • Initialize with a random integer. You can generate a random int as follows: Random rand = new System.Random(); int random_int = rand.Next();
  • To get a random number generator that covers the full range, use a loop like this to draw a random number from the whole range uniformly:

    BigInteger random_number = 0;
    for (int i = 0; i < length/32; i++)
        random_number = (random_number << 32) + rand.Next();

** Here, the length of the number you are testing ($N$) is assumed to be measured in bits. Use BigInteger.Log(N, 2)+1 and round up to compute the number of bits needed to represent $N$. ** Once you have computed your random number (let's call it $a$) using that code snippet, make sure it is in the proper range (a value between $1$ and $N-1$ (inclusive)), as required by the contrapositive of Fermat's little theorem. If it does not, then discard it and draw another one until you do. In particular, also be sure that your chosen random number is not $0$ ($a=0$ is not a legitimate value for the contrapositive of Fermat's little theorem.)

• You may not use library functions to compute modular exponentiation such as BigInteger.modPow(). The point is for you to gain insight into the modular exponentiation algorithm itself.
  • That said, you could certainly check your answer against modPow()'s result.
• There is an IsEven method on BigInteger to facilitate your implementation of the modular exponentiation algorithm.

Write a type-written report containing the following distinct sections as a single PDF document, and submit it by following the submission directions in the course syllabus.

1. Place your name, Net ID, and section number at the top of the first page.
2. Include an estimate of the amount of time you spent on this project at the top of the first page.
3. [25 points] Include at least one screenshot of your application with a working example that is at least 50 decimal digits long.
   • Find a prime that is at least 50 decimal digits long by consulting the web. Be sure to give credit to your source.
   • Note: to capture just the top window in your screenshot, use the key-chord alt-PrtSc (i.e., print screen)
4. [10 points] Include the equation for computing the probability of correctness that appears in the output.
5. Include all of the code that you wrote. In most cases, the code will be the contents of the Form1.cs file. Your code must include the following:
   • [25 points] A correct implementation and application of modular exponentiation.
   • [30 points] A correct implementation and application of the Fermat primality tester.
   • [10 points] The remainder of your code.
   • Document your algorithm with legible comments in important places in the code that make it obvious to the reader what your solution is doing. This documentation also provides evidence of your comprehension. With the aid of adequate documentation, the correctness of your approach should be easy for the reader (e.g., TA) to verify. If the TA cannot easily determine the code's correctness, then fewer points will be awarded.

• Note that there is no performance requirement for this project. Correctness is the only criterion.

Remember this important direction from the syllabus: “The project reports are due by midnight on the specified due date.”