[ Index ]

PHP Cross Reference of DokuWiki




/vendor/phpseclib/phpseclib/phpseclib/Math/BigInteger/Engines/PHP/Reductions/ -> Montgomery.php (summary)

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

Defines 3 functions


Functions that are not part of a class:

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