| [ Index ] |
PHP Cross Reference of Joomla 4.2.2 documentation |
[Source view] [Print] [Project Stats]
BCMath Barrett Modular Exponentiation Engine PHP version 5 and 7
| Author: | Jim Wigginton <[email protected]> |
| Copyright: | 2017 Jim Wigginton |
| License: | http://www.opensource.org/licenses/mit-license.html MIT License |
| File Size: | 193 lines (7 kb) |
| Included or required: | 0 times |
| Referenced: | 0 times |
| Includes or requires: | 0 files |
| 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. param: string $n param: string $m return: string |
| 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. param: string $x param: string $n return: string |
| Generated: Wed Sep 7 05:41:13 2022 | Chilli.vc Blog - For Webmaster,Blog-Writer,System Admin and Domainer |