Primality Test

Instructions

  1. Launch VisualStudio and start a new windows C# project. (Project type should be set to "Visual C#" then select the "Windows Forms Application" template).
  2. Create a form with three 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").
  3. Name one textbox "input" one "output", and the other is for the k value (you will enter an arbitrary k value as described in the book). (Right-click on the textbox to view properties. One of the properties is the name. The default name will be textBox1 or something similar).
  4. 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").
  5. 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.
  6. You should now be editing code in a method called "solve_click()" in a file called "Form1.cs"
  7. Code up the primality test pseudocode from Figure 1.8 of the text. You may set k to any value you like (see p. 27). Be sure to also implement modular exponentiation (pseudo-code in Figure 1.4 on p. 19). Your primality test should use your modular exponentiation function and should work properly for numbers as large as 230.
    1. The contents of the input textbox can be accessed as

      2.              input.Text

    2. and a string can be converted to an integer using

      3.              Convert.ToInt32(input.Text)

    3. You can set the value of the text in a textbox in much the same way:

      4.              output.Text = "the output"

    4. and similarly for the box where you enter in the k value you want to use for the current test.
  8. Be sure to avoid re-using the same random values for your repeated tests.
  9. 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.

Submission

A report consisting of:

  1. [20 points] At least one screenshot of your application with a working example
  2. All of the code that you wrote. For this and all future code submissions note the following. In each project, be sure to always document your algorithm with legible comments in important places in your code that make it obvious to the reader what your solution is doing. Note the time/space complexity of each key portion of your code. 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 your code spans multiple files, make sure that you include all of it, and make sure that it is organized in a way that makes it easy for the reader (TA) to follow. Your code must include the following:
    1. [20 points] A correct implementation of modular exponentiation.
    2. [20 points] A correct implementation of the Fermat primality tester.
    3. [10 points] The remainder of your code.
  3. [10 points] Explain the time and space complexity of your algorithm by showing and summing up the complexity of each subsection of your code.
  4. [10 points] Discuss the equation you used to compute the probability of correctness p that appears in the output.

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

Submit as a PDF by following the submission directions in the course syllabus.