[ Index ]

PHP Cross Reference of DokuWiki




/vendor/phpseclib/phpseclib/phpseclib/Math/BigInteger/Engines/BCMath/Reductions/ -> Barrett.php (summary)

BCMath Barrett 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: 187 lines (7 kb)
Included or required:0 times
Referenced: 0 times
Includes or requires: 0 files

Defines 2 functions


Functions that are not part of a class:

reduce($n, $m)   X-Ref
Barrett Modular Reduction

See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=14 HAC 14.3.3} /
{@link http://math.libtomcrypt.com/files/tommath.pdf#page=165 MPM 6.2.5} for more information.  Modified slightly,
so as not to require negative numbers (initially, this script didn't support negative numbers).

Employs "folding", as described at
{@link http://www.cosic.esat.kuleuven.be/publications/thesis-149.pdf#page=66 thesis-149.pdf#page=66}.  To quote from
it, "the idea [behind folding] is to find a value x' such that x (mod m) = x' (mod m), with x' being smaller than x."

Unfortunately, the "Barrett Reduction with Folding" algorithm described in thesis-149.pdf is not, as written, all that
usable on account of (1) its not using reasonable radix points as discussed in
{@link http://math.libtomcrypt.com/files/tommath.pdf#page=162 MPM 6.2.2} and (2) the fact that, even with reasonable
radix points, it only works when there are an even number of digits in the denominator.  The reason for (2) is that
(x >> 1) + (x >> 1) != x / 2 + x / 2.  If x is even, they're the same, but if x is odd, they're not.  See the in-line
comments for details.

return: string
param: string $n
param: string $m

regularBarrett($x, $n)   X-Ref
(Regular) Barrett Modular Reduction

For numbers with more than four digits BigInteger::_barrett() is faster.  The difference between that and this
is that this function does not fold the denominator into a smaller form.

return: string
param: string $x
param: string $n