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