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