backup
/
src
/
JetBackup
/
3rdparty
/
phpseclib3
/
Math
/
BigInteger
/
Engines
/
PHP
/
Reductions
/
Barrett.php
backup
/
src
/
JetBackup
/
3rdparty
/
phpseclib3
/
Math
/
BigInteger
/
Engines
/
PHP
/
Reductions
Last commit date
.htaccess
1 year ago
Barrett.php
1 year ago
Classic.php
1 year ago
EvalBarrett.php
1 year ago
Montgomery.php
1 year ago
MontgomeryMult.php
1 year ago
PowerOfTwo.php
1 year ago
index.html
1 year ago
web.config
1 year ago
Barrett.php
269 lines
| 1 | <?php |
| 2 | |
| 3 | /** |
| 4 | * PHP Barrett Modular Exponentiation Engine |
| 5 | * |
| 6 | * PHP version 5 and 7 |
| 7 | * |
| 8 | * @author Jim Wigginton <terrafrost@php.net> |
| 9 | * @copyright 2017 Jim Wigginton |
| 10 | * @license http://www.opensource.org/licenses/mit-license.html MIT License |
| 11 | * @link http://pear.php.net/package/Math_BigInteger |
| 12 | */ |
| 13 | |
| 14 | declare(strict_types=1); |
| 15 | |
| 16 | namespace phpseclib3\Math\BigInteger\Engines\PHP\Reductions; |
| 17 | |
| 18 | use phpseclib3\Math\BigInteger\Engines\PHP; |
| 19 | use phpseclib3\Math\BigInteger\Engines\PHP\Base; |
| 20 | |
| 21 | /** |
| 22 | * PHP Barrett Modular Exponentiation Engine |
| 23 | * |
| 24 | * @author Jim Wigginton <terrafrost@php.net> |
| 25 | */ |
| 26 | abstract class Barrett extends Base |
| 27 | { |
| 28 | /** |
| 29 | * Barrett Modular Reduction |
| 30 | * |
| 31 | * See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=14 HAC 14.3.3} / |
| 32 | * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=165 MPM 6.2.5} for more information. Modified slightly, |
| 33 | * so as not to require negative numbers (initially, this script didn't support negative numbers). |
| 34 | * |
| 35 | * Employs "folding", as described at |
| 36 | * {@link http://www.cosic.esat.kuleuven.be/publications/thesis-149.pdf#page=66 thesis-149.pdf#page=66}. To quote from |
| 37 | * 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." |
| 38 | * |
| 39 | * Unfortunately, the "Barrett Reduction with Folding" algorithm described in thesis-149.pdf is not, as written, all that |
| 40 | * usable on account of (1) its not using reasonable radix points as discussed in |
| 41 | * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=162 MPM 6.2.2} and (2) the fact that, even with reasonable |
| 42 | * radix points, it only works when there are an even number of digits in the denominator. The reason for (2) is that |
| 43 | * (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 |
| 44 | * comments for details. |
| 45 | * |
| 46 | * @param class-string<PHP> $class |
| 47 | */ |
| 48 | protected static function reduce(array $n, array $m, string $class): array |
| 49 | { |
| 50 | static $cache = [ |
| 51 | self::VARIABLE => [], |
| 52 | self::DATA => [], |
| 53 | ]; |
| 54 | |
| 55 | $m_length = count($m); |
| 56 | |
| 57 | // if (self::compareHelper($n, $static::square($m)) >= 0) { |
| 58 | if (count($n) > 2 * $m_length) { |
| 59 | $lhs = new $class(); |
| 60 | $rhs = new $class(); |
| 61 | $lhs->value = $n; |
| 62 | $rhs->value = $m; |
| 63 | [, $temp] = $lhs->divide($rhs); |
| 64 | return $temp->value; |
| 65 | } |
| 66 | |
| 67 | // if (m.length >> 1) + 2 <= m.length then m is too small and n can't be reduced |
| 68 | if ($m_length < 5) { |
| 69 | return self::regularBarrett($n, $m, $class); |
| 70 | } |
| 71 | // n = 2 * m.length |
| 72 | |
| 73 | if (($key = array_search($m, $cache[self::VARIABLE])) === false) { |
| 74 | $key = count($cache[self::VARIABLE]); |
| 75 | $cache[self::VARIABLE][] = $m; |
| 76 | |
| 77 | $lhs = new $class(); |
| 78 | $lhs_value = &$lhs->value; |
| 79 | $lhs_value = self::array_repeat(0, $m_length + ($m_length >> 1)); |
| 80 | $lhs_value[] = 1; |
| 81 | $rhs = new $class(); |
| 82 | $rhs->value = $m; |
| 83 | |
| 84 | [$u, $m1] = $lhs->divide($rhs); |
| 85 | $u = $u->value; |
| 86 | $m1 = $m1->value; |
| 87 | |
| 88 | $cache[self::DATA][] = [ |
| 89 | 'u' => $u, // m.length >> 1 (technically (m.length >> 1) + 1) |
| 90 | 'm1' => $m1, // m.length |
| 91 | ]; |
| 92 | } else { |
| 93 | extract($cache[self::DATA][$key]); |
| 94 | } |
| 95 | |
| 96 | $cutoff = $m_length + ($m_length >> 1); |
| 97 | $lsd = array_slice($n, 0, $cutoff); // m.length + (m.length >> 1) |
| 98 | $msd = array_slice($n, $cutoff); // m.length >> 1 |
| 99 | |
| 100 | $lsd = self::trim($lsd); |
| 101 | $temp = $class::multiplyHelper($msd, false, $m1, false); // m.length + (m.length >> 1) |
| 102 | $n = $class::addHelper($lsd, false, $temp[self::VALUE], false); // m.length + (m.length >> 1) + 1 (so basically we're adding two same length numbers) |
| 103 | //if ($m_length & 1) { |
| 104 | // return self::regularBarrett($n[self::VALUE], $m, $class); |
| 105 | //} |
| 106 | |
| 107 | // (m.length + (m.length >> 1) + 1) - (m.length - 1) == (m.length >> 1) + 2 |
| 108 | $temp = array_slice($n[self::VALUE], $m_length - 1); |
| 109 | // if even: ((m.length >> 1) + 2) + (m.length >> 1) == m.length + 2 |
| 110 | // if odd: ((m.length >> 1) + 2) + (m.length >> 1) == (m.length - 1) + 2 == m.length + 1 |
| 111 | $temp = $class::multiplyHelper($temp, false, $u, false); |
| 112 | // if even: (m.length + 2) - ((m.length >> 1) + 1) = m.length - (m.length >> 1) + 1 |
| 113 | // if odd: (m.length + 1) - ((m.length >> 1) + 1) = m.length - (m.length >> 1) |
| 114 | $temp = array_slice($temp[self::VALUE], ($m_length >> 1) + 1); |
| 115 | // if even: (m.length - (m.length >> 1) + 1) + m.length = 2 * m.length - (m.length >> 1) + 1 |
| 116 | // if odd: (m.length - (m.length >> 1)) + m.length = 2 * m.length - (m.length >> 1) |
| 117 | $temp = $class::multiplyHelper($temp, false, $m, false); |
| 118 | |
| 119 | // at this point, if m had an odd number of digits, we'd be subtracting a 2 * m.length - (m.length >> 1) digit |
| 120 | // number from a m.length + (m.length >> 1) + 1 digit number. ie. there'd be an extra digit and the while loop |
| 121 | // following this comment would loop a lot (hence our calling _regularBarrett() in that situation). |
| 122 | |
| 123 | $result = $class::subtractHelper($n[self::VALUE], false, $temp[self::VALUE], false); |
| 124 | |
| 125 | while (self::compareHelper($result[self::VALUE], $result[self::SIGN], $m, false) >= 0) { |
| 126 | $result = $class::subtractHelper($result[self::VALUE], $result[self::SIGN], $m, false); |
| 127 | } |
| 128 | |
| 129 | return $result[self::VALUE]; |
| 130 | } |
| 131 | |
| 132 | /** |
| 133 | * (Regular) Barrett Modular Reduction |
| 134 | * |
| 135 | * For numbers with more than four digits BigInteger::_barrett() is faster. The difference between that and this |
| 136 | * is that this function does not fold the denominator into a smaller form. |
| 137 | */ |
| 138 | private static function regularBarrett(array $x, array $n, string $class): array |
| 139 | { |
| 140 | static $cache = [ |
| 141 | self::VARIABLE => [], |
| 142 | self::DATA => [], |
| 143 | ]; |
| 144 | |
| 145 | $n_length = count($n); |
| 146 | |
| 147 | if (count($x) > 2 * $n_length) { |
| 148 | $lhs = new $class(); |
| 149 | $rhs = new $class(); |
| 150 | $lhs->value = $x; |
| 151 | $rhs->value = $n; |
| 152 | [, $temp] = $lhs->divide($rhs); |
| 153 | return $temp->value; |
| 154 | } |
| 155 | |
| 156 | if (($key = array_search($n, $cache[self::VARIABLE])) === false) { |
| 157 | $key = count($cache[self::VARIABLE]); |
| 158 | $cache[self::VARIABLE][] = $n; |
| 159 | $lhs = new $class(); |
| 160 | $lhs_value = &$lhs->value; |
| 161 | $lhs_value = self::array_repeat(0, 2 * $n_length); |
| 162 | $lhs_value[] = 1; |
| 163 | $rhs = new $class(); |
| 164 | $rhs->value = $n; |
| 165 | [$temp, ] = $lhs->divide($rhs); // m.length |
| 166 | $cache[self::DATA][] = $temp->value; |
| 167 | } |
| 168 | |
| 169 | // 2 * m.length - (m.length - 1) = m.length + 1 |
| 170 | $temp = array_slice($x, $n_length - 1); |
| 171 | // (m.length + 1) + m.length = 2 * m.length + 1 |
| 172 | $temp = $class::multiplyHelper($temp, false, $cache[self::DATA][$key], false); |
| 173 | // (2 * m.length + 1) - (m.length - 1) = m.length + 2 |
| 174 | $temp = array_slice($temp[self::VALUE], $n_length + 1); |
| 175 | |
| 176 | // m.length + 1 |
| 177 | $result = array_slice($x, 0, $n_length + 1); |
| 178 | // m.length + 1 |
| 179 | $temp = self::multiplyLower($temp, false, $n, false, $n_length + 1, $class); |
| 180 | // $temp == array_slice($class::regularMultiply($temp, false, $n, false)->value, 0, $n_length + 1) |
| 181 | |
| 182 | if (self::compareHelper($result, false, $temp[self::VALUE], $temp[self::SIGN]) < 0) { |
| 183 | $corrector_value = self::array_repeat(0, $n_length + 1); |
| 184 | $corrector_value[count($corrector_value)] = 1; |
| 185 | $result = $class::addHelper($result, false, $corrector_value, false); |
| 186 | $result = $result[self::VALUE]; |
| 187 | } |
| 188 | |
| 189 | // at this point, we're subtracting a number with m.length + 1 digits from another number with m.length + 1 digits |
| 190 | $result = $class::subtractHelper($result, false, $temp[self::VALUE], $temp[self::SIGN]); |
| 191 | while (self::compareHelper($result[self::VALUE], $result[self::SIGN], $n, false) > 0) { |
| 192 | $result = $class::subtractHelper($result[self::VALUE], $result[self::SIGN], $n, false); |
| 193 | } |
| 194 | |
| 195 | return $result[self::VALUE]; |
| 196 | } |
| 197 | |
| 198 | /** |
| 199 | * Performs long multiplication up to $stop digits |
| 200 | * |
| 201 | * If you're going to be doing array_slice($product->value, 0, $stop), some cycles can be saved. |
| 202 | * |
| 203 | * @see self::regularBarrett() |
| 204 | */ |
| 205 | private static function multiplyLower(array $x_value, bool $x_negative, array $y_value, bool $y_negative, int $stop, string $class): array |
| 206 | { |
| 207 | $x_length = count($x_value); |
| 208 | $y_length = count($y_value); |
| 209 | |
| 210 | if (!$x_length || !$y_length) { // a 0 is being multiplied |
| 211 | return [ |
| 212 | self::VALUE => [], |
| 213 | self::SIGN => false, |
| 214 | ]; |
| 215 | } |
| 216 | |
| 217 | if ($x_length < $y_length) { |
| 218 | $temp = $x_value; |
| 219 | $x_value = $y_value; |
| 220 | $y_value = $temp; |
| 221 | |
| 222 | $x_length = count($x_value); |
| 223 | $y_length = count($y_value); |
| 224 | } |
| 225 | |
| 226 | $product_value = self::array_repeat(0, $x_length + $y_length); |
| 227 | |
| 228 | // the following for loop could be removed if the for loop following it |
| 229 | // (the one with nested for loops) initially set $i to 0, but |
| 230 | // doing so would also make the result in one set of unnecessary adds, |
| 231 | // since on the outermost loops first pass, $product->value[$k] is going |
| 232 | // to always be 0 |
| 233 | |
| 234 | $carry = 0; |
| 235 | |
| 236 | for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0, $k = $i |
| 237 | $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0 |
| 238 | $carry = $class::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31); |
| 239 | $product_value[$j] = (int) ($temp - $class::BASE_FULL * $carry); |
| 240 | } |
| 241 | |
| 242 | if ($j < $stop) { |
| 243 | $product_value[$j] = $carry; |
| 244 | } |
| 245 | |
| 246 | // the above for loop is what the previous comment was talking about. the |
| 247 | // following for loop is the "one with nested for loops" |
| 248 | |
| 249 | for ($i = 1; $i < $y_length; ++$i) { |
| 250 | $carry = 0; |
| 251 | |
| 252 | for ($j = 0, $k = $i; $j < $x_length && $k < $stop; ++$j, ++$k) { |
| 253 | $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry; |
| 254 | $carry = $class::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31); |
| 255 | $product_value[$k] = (int) ($temp - $class::BASE_FULL * $carry); |
| 256 | } |
| 257 | |
| 258 | if ($k < $stop) { |
| 259 | $product_value[$k] = $carry; |
| 260 | } |
| 261 | } |
| 262 | |
| 263 | return [ |
| 264 | self::VALUE => self::trim($product_value), |
| 265 | self::SIGN => $x_negative != $y_negative, |
| 266 | ]; |
| 267 | } |
| 268 | } |
| 269 |