##### Differences

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

 cs-312:project-1 [2015/01/13 23:46]ringger [Instructions] cs-312:project-1 [2015/01/26 15:21]ringger [Report] Both sides previous revision Previous revision 2015/01/26 15:21 ringger [Report] 2015/01/14 21:21 ringger [Implementation Notes] 2015/01/13 23:46 ringger [Instructions] 2015/01/13 23:46 ringger [Instructions] 2015/01/12 14:55 ringger [Implementation Notes] 2015/01/12 14:53 ringger [Implementation Notes] 2015/01/12 14:52 ringger [Implementation Notes] 2015/01/12 14:30 ringger [Implementation Notes] 2015/01/12 14:28 ringger [Implementation Notes] 2015/01/12 14:26 ringger [Implementation Notes] 2015/01/12 14:26 ringger [Implementation Notes] 2015/01/12 14:25 ringger 2015/01/12 07:47 ringger [Report] 2015/01/12 07:47 ringger [Implementation Notes] 2015/01/12 07:45 ringger [Implementation Notes] 2015/01/12 07:43 ringger 2015/01/12 07:41 ringger 2014/12/31 16:21 ringger 2014/12/31 15:08 ringger created Next revision Previous revision 2015/01/26 15:21 ringger [Report] 2015/01/14 21:21 ringger [Implementation Notes] 2015/01/13 23:46 ringger [Instructions] 2015/01/13 23:46 ringger [Instructions] 2015/01/12 14:55 ringger [Implementation Notes] 2015/01/12 14:53 ringger [Implementation Notes] 2015/01/12 14:52 ringger [Implementation Notes] 2015/01/12 14:30 ringger [Implementation Notes] 2015/01/12 14:28 ringger [Implementation Notes] 2015/01/12 14:26 ringger [Implementation Notes] 2015/01/12 14:26 ringger [Implementation Notes] 2015/01/12 14:25 ringger 2015/01/12 07:47 ringger [Report] 2015/01/12 07:47 ringger [Implementation Notes] 2015/01/12 07:45 ringger [Implementation Notes] 2015/01/12 07:43 ringger 2015/01/12 07:41 ringger 2014/12/31 16:21 ringger 2014/12/31 15:08 ringger created Line 56: Line 56: ** Here, the <​tt>​length​ of the number you are testing ($N$) is assumed to be measured in bits.  Use <​tt>​BigInteger.Log(N,​ 2)+1​ and round up to compute the number of bits needed to represent $N$. ** Here, the <​tt>​length​ of the number you are testing ($N$) is assumed to be measured in bits.  Use <​tt>​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.) ** 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()​. 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()​. 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()'​s result. ** That said, you could certainly check your answer against <​tt>​modPow()'​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​ 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​ 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.