Differences

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

Link to this comparison view

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.
cs-312/project-1.txt ยท Last modified: 2015/01/26 15:21 by ringger
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0