| [ Index ] |
PHP Cross Reference of DokuWiki |
[Source view] [Print] [Project Stats]
PHP Montgomery Modular Exponentiation Engine PHP version 5 and 7
| Author: | Jim Wigginton |
| Copyright: | 2017 Jim Wigginton |
| License: | http://www.opensource.org/licenses/mit-license.html MIT License |
| Link: | http://pear.php.net/package/Math_BigInteger |
| File Size: | 126 lines (5 kb) |
| Included or required: | 0 times |
| Referenced: | 0 times |
| Includes or requires: | 0 files |
| prepareReduce(array $x, array $n, $class) X-Ref |
| Prepare a number for use in Montgomery Modular Reductions return: array param: array $x param: array $n param: string $class |
| reduce(array $x, array $n, $class) X-Ref |
| Montgomery Multiply Interleaves the montgomery reduction and long multiplication algorithms together as described in {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=13 HAC 14.36} return: array param: array $x param: array $n param: string $class |
| modInverse67108864(array $x, $class) X-Ref |
| Modular Inverse of a number mod 2**26 (eg. 67108864) Based off of the bnpInvDigit function implemented and justified in the following URL: {@link http://www-cs-students.stanford.edu/~tjw/jsbn/jsbn.js} The following URL provides more info: {@link http://groups.google.com/group/sci.crypt/msg/7a137205c1be7d85} As for why we do all the bitmasking... strange things can happen when converting from floats to ints. For instance, on some computers, var_dump((int) -4294967297) yields int(-1) and on others, it yields int(-2147483648). To avoid problems stemming from this, we use bitmasks to guarantee that ints aren't auto-converted to floats. The outermost bitmask is present because without it, there's no guarantee that the "residue" returned would be the so-called "common residue". We use fmod, in the last step, because the maximum possible $x is 26 bits and the maximum $result is 16 bits. Thus, we have to be able to handle up to 40 bits, which only 64-bit floating points will support. Thanks to Pedro Gimeno Fortea for input! return: int param: array $x param: string $class |