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

Both sides previous revision Previous revision | Last revision Both sides next revision | ||

cs-312:project-1 [2015/01/13 23:46] ringger [Instructions] |
cs-312:project-1 [2015/01/14 21:21] ringger [Implementation Notes] |
||
---|---|---|---|

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. |