| [ Index ] |
PHP Cross Reference of DokuWiki |
[Source view] [Print] [Project Stats]
PHP 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: | 281 lines (11 kb) |
| Included or required: | 0 times |
| Referenced: | 0 times |
| Includes or requires: | 0 files |
| reduce(array $n, array $m, $class) 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: array param: array $n param: array $m param: class-string<PHP> $class |
| regularBarrett(array $x, array $n, $class) 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: array param: array $x param: array $n param: string $class |
| multiplyLower(array $x_value, $x_negative, array $y_value, $y_negative, $stop, $class) X-Ref |
| Performs long multiplication up to $stop digits If you're going to be doing array_slice($product->value, 0, $stop), some cycles can be saved. return: array param: array $x_value param: bool $x_negative param: array $y_value param: bool $y_negative param: int $stop param: string $class see: self::regularBarrett() |