This shows you the differences between two versions of the page.

Both sides previous revision Previous revision Next revision | Previous revision | ||

cs-312:project-1 [2015/01/13 23:46] ringger [Instructions] |
cs-312:project-1 [2015/01/26 15:21] ringger [Report] |
||
---|---|---|---|

Line 56: | Line 56: | ||

** Here, the <tt>length</tt> of the number you are testing ($N$) is assumed to be measured in bits. Use <tt>BigInteger.Log(N, 2)+1</tt> and round up to compute the number of bits needed to represent $N$. | ** Here, the <tt>length</tt> of the number you are testing ($N$) is assumed to be measured in bits. Use <tt>BigInteger.Log(N, 2)+1</tt> 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.) | ** 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 <tt>BigInteger.modPow()</tt>. The point is for you to gain insight into the modular exponentiation algorithm itself. | * You may '''not''' use library functions to compute modular exponentiation such as <tt>BigInteger.modPow()</tt>. The point is for you to gain insight into the modular exponentiation algorithm itself. | ||

** That said, you could certainly check your answer against <tt>modPow()</tt>'s result. | ** That said, you could certainly check your answer against <tt>modPow()</tt>'s result. | ||

Line 65: | Line 66: | ||

# Place your name, Net ID, and section number at the top of the first page. | # Place your name, Net ID, and section number at the top of the first page. | ||

- | # Also include an estimate of the amount of time you spent on this project at the top of the first page. | + | # Include an estimate of the amount of time you spent on this project at the top of the first page. |

- | # [25 points] At least one screenshot of your application with a working example that is at least 50 decimal digits long. | + | # [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. | #* 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) | #* Note: to capture just the top window in your screenshot, use the key-chord alt-PrtSc (i.e., print screen) | ||

- | # [10 points] The equation you used to compute the probability of ''correctness'' p that appears in the output. | + | # [10 points] Include the equation for computing the probability of ''correctness'' that appears in the output. |

- | # All of the code that you wrote. In most cases, the code will be the contents of the <tt>Form1.cs</tt> file. Your code must include the following: | + | # Include all of the code that you wrote. In most cases, the code will be the contents of the <tt>Form1.cs</tt> file. Your code must include the following: |

#* [25 points] A correct implementation and application of modular exponentiation. | #* [25 points] A correct implementation and application of modular exponentiation. | ||

#* [30 points] A correct implementation and application of the Fermat primality tester. | #* [30 points] A correct implementation and application of the Fermat primality tester. | ||

- | #* [10 points] Remainder of your code. | + | #* [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. | #* 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. | ||