| [ Index ] |
PHP Cross Reference of Joomla 4.2.2 documentation |
[Summary view] [Print] [Text view]
1 <?php 2 3 /** 4 * Pure-PHP BigInteger Engine 5 * 6 * PHP version 5 and 7 7 * 8 * @category Math 9 * @package BigInteger 10 * @author Jim Wigginton <[email protected]> 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 16 namespace phpseclib3\Math\BigInteger\Engines; 17 18 use ParagonIE\ConstantTime\Hex; 19 use phpseclib3\Exception\BadConfigurationException; 20 21 /** 22 * Pure-PHP Engine. 23 * 24 * @package PHP 25 * @author Jim Wigginton <[email protected]> 26 * @access public 27 */ 28 abstract class PHP extends Engine 29 { 30 /**#@+ 31 * Array constants 32 * 33 * Rather than create a thousands and thousands of new BigInteger objects in repeated function calls to add() and 34 * multiply() or whatever, we'll just work directly on arrays, taking them in as parameters and returning them. 35 * 36 * @access protected 37 */ 38 /** 39 * $result[self::VALUE] contains the value. 40 */ 41 const VALUE = 0; 42 /** 43 * $result[self::SIGN] contains the sign. 44 */ 45 const SIGN = 1; 46 /**#@-*/ 47 48 /** 49 * Karatsuba Cutoff 50 * 51 * At what point do we switch between Karatsuba multiplication and schoolbook long multiplication? 52 * 53 * @access private 54 */ 55 const KARATSUBA_CUTOFF = 25; 56 57 /** 58 * Can Bitwise operations be done fast? 59 * 60 * @see parent::bitwise_leftRotate() 61 * @see parent::bitwise_rightRotate() 62 * @access protected 63 */ 64 const FAST_BITWISE = true; 65 66 /** 67 * Engine Directory 68 * 69 * @see parent::setModExpEngine 70 * @access protected 71 */ 72 const ENGINE_DIR = 'PHP'; 73 74 /** 75 * Default constructor 76 * 77 * @param mixed $x integer Base-10 number or base-$base number if $base set. 78 * @param int $base 79 * @return PHP 80 * @see parent::__construct() 81 */ 82 public function __construct($x = 0, $base = 10) 83 { 84 if (!isset(static::$isValidEngine[static::class])) { 85 static::$isValidEngine[static::class] = static::isValidEngine(); 86 } 87 if (!static::$isValidEngine[static::class]) { 88 throw new BadConfigurationException(static::class . ' is not setup correctly on this system'); 89 } 90 91 $this->value = []; 92 parent::__construct($x, $base); 93 } 94 95 /** 96 * Initialize a PHP BigInteger Engine instance 97 * 98 * @param int $base 99 * @see parent::__construct() 100 */ 101 protected function initialize($base) 102 { 103 switch (abs($base)) { 104 case 16: 105 $x = (strlen($this->value) & 1) ? '0' . $this->value : $this->value; 106 $temp = new static(Hex::decode($x), 256); 107 $this->value = $temp->value; 108 break; 109 case 10: 110 $temp = new static(); 111 112 $multiplier = new static(); 113 $multiplier->value = [static::MAX10]; 114 115 $x = $this->value; 116 117 if ($x[0] == '-') { 118 $this->is_negative = true; 119 $x = substr($x, 1); 120 } 121 122 $x = str_pad( 123 $x, 124 strlen($x) + ((static::MAX10LEN - 1) * strlen($x)) % static::MAX10LEN, 125 0, 126 STR_PAD_LEFT 127 ); 128 while (strlen($x)) { 129 $temp = $temp->multiply($multiplier); 130 $temp = $temp->add(new static($this->int2bytes(substr($x, 0, static::MAX10LEN)), 256)); 131 $x = substr($x, static::MAX10LEN); 132 } 133 134 $this->value = $temp->value; 135 } 136 } 137 138 /** 139 * Pads strings so that unpack may be used on them 140 * 141 * @param string $str 142 * @return string 143 */ 144 protected function pad($str) 145 { 146 $length = strlen($str); 147 148 $pad = 4 - (strlen($str) % 4); 149 150 return str_pad($str, $length + $pad, "\0", STR_PAD_LEFT); 151 } 152 153 /** 154 * Converts a BigInteger to a base-10 number. 155 * 156 * @return string 157 */ 158 public function toString() 159 { 160 if (!count($this->value)) { 161 return '0'; 162 } 163 164 $temp = clone $this; 165 $temp->bitmask = false; 166 $temp->is_negative = false; 167 168 $divisor = new static(); 169 $divisor->value = [static::MAX10]; 170 $result = ''; 171 while (count($temp->value)) { 172 list($temp, $mod) = $temp->divide($divisor); 173 $result = str_pad( 174 isset($mod->value[0]) ? $mod->value[0] : '', 175 static::MAX10LEN, 176 '0', 177 STR_PAD_LEFT 178 ) . $result; 179 } 180 $result = ltrim($result, '0'); 181 if (empty($result)) { 182 $result = '0'; 183 } 184 185 if ($this->is_negative) { 186 $result = '-' . $result; 187 } 188 189 return $result; 190 } 191 192 /** 193 * Converts a BigInteger to a byte string (eg. base-256). 194 * 195 * @param bool $twos_compliment 196 * @return string 197 */ 198 public function toBytes($twos_compliment = false) 199 { 200 if ($twos_compliment) { 201 return $this->toBytesHelper(); 202 } 203 204 if (!count($this->value)) { 205 return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : ''; 206 } 207 208 $result = $this->bitwise_small_split(8); 209 $result = implode('', array_map('chr', $result)); 210 211 return $this->precision > 0 ? 212 str_pad( 213 substr($result, -(($this->precision + 7) >> 3)), 214 ($this->precision + 7) >> 3, 215 chr(0), 216 STR_PAD_LEFT 217 ) : 218 $result; 219 } 220 221 /** 222 * Performs addition. 223 * 224 * @param array $x_value 225 * @param bool $x_negative 226 * @param array $y_value 227 * @param bool $y_negative 228 * @return array 229 */ 230 protected static function addHelper(array $x_value, $x_negative, array $y_value, $y_negative) 231 { 232 $x_size = count($x_value); 233 $y_size = count($y_value); 234 235 if ($x_size == 0) { 236 return [ 237 self::VALUE => $y_value, 238 self::SIGN => $y_negative 239 ]; 240 } elseif ($y_size == 0) { 241 return [ 242 self::VALUE => $x_value, 243 self::SIGN => $x_negative 244 ]; 245 } 246 247 // subtract, if appropriate 248 if ($x_negative != $y_negative) { 249 if ($x_value == $y_value) { 250 return [ 251 self::VALUE => [], 252 self::SIGN => false 253 ]; 254 } 255 256 $temp = self::subtractHelper($x_value, false, $y_value, false); 257 $temp[self::SIGN] = self::compareHelper($x_value, false, $y_value, false) > 0 ? 258 $x_negative : $y_negative; 259 260 return $temp; 261 } 262 263 if ($x_size < $y_size) { 264 $size = $x_size; 265 $value = $y_value; 266 } else { 267 $size = $y_size; 268 $value = $x_value; 269 } 270 271 $value[count($value)] = 0; // just in case the carry adds an extra digit 272 273 $carry = 0; 274 for ($i = 0, $j = 1; $j < $size; $i += 2, $j += 2) { 275 //$sum = $x_value[$j] * static::BASE_FULL + $x_value[$i] + $y_value[$j] * static::BASE_FULL + $y_value[$i] + $carry; 276 $sum = ($x_value[$j] + $y_value[$j]) * static::BASE_FULL + $x_value[$i] + $y_value[$i] + $carry; 277 $carry = $sum >= static::MAX_DIGIT2; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1 278 $sum = $carry ? $sum - static::MAX_DIGIT2 : $sum; 279 280 $temp = static::BASE === 26 ? intval($sum / 0x4000000) : ($sum >> 31); 281 282 $value[$i] = (int)($sum - static::BASE_FULL * $temp); // eg. a faster alternative to fmod($sum, 0x4000000) 283 $value[$j] = $temp; 284 } 285 286 if ($j == $size) { // ie. if $y_size is odd 287 $sum = $x_value[$i] + $y_value[$i] + $carry; 288 $carry = $sum >= static::BASE_FULL; 289 $value[$i] = $carry ? $sum - static::BASE_FULL : $sum; 290 ++$i; // ie. let $i = $j since we've just done $value[$i] 291 } 292 293 if ($carry) { 294 for (; $value[$i] == static::MAX_DIGIT; ++$i) { 295 $value[$i] = 0; 296 } 297 ++$value[$i]; 298 } 299 300 return [ 301 self::VALUE => self::trim($value), 302 self::SIGN => $x_negative 303 ]; 304 } 305 306 /** 307 * Performs subtraction. 308 * 309 * @param array $x_value 310 * @param bool $x_negative 311 * @param array $y_value 312 * @param bool $y_negative 313 * @return array 314 */ 315 public static function subtractHelper(array $x_value, $x_negative, array $y_value, $y_negative) 316 { 317 $x_size = count($x_value); 318 $y_size = count($y_value); 319 320 if ($x_size == 0) { 321 return [ 322 self::VALUE => $y_value, 323 self::SIGN => !$y_negative 324 ]; 325 } elseif ($y_size == 0) { 326 return [ 327 self::VALUE => $x_value, 328 self::SIGN => $x_negative 329 ]; 330 } 331 332 // add, if appropriate (ie. -$x - +$y or +$x - -$y) 333 if ($x_negative != $y_negative) { 334 $temp = self::addHelper($x_value, false, $y_value, false); 335 $temp[self::SIGN] = $x_negative; 336 337 return $temp; 338 } 339 340 $diff = self::compareHelper($x_value, $x_negative, $y_value, $y_negative); 341 342 if (!$diff) { 343 return [ 344 self::VALUE => [], 345 self::SIGN => false 346 ]; 347 } 348 349 // switch $x and $y around, if appropriate. 350 if ((!$x_negative && $diff < 0) || ($x_negative && $diff > 0)) { 351 $temp = $x_value; 352 $x_value = $y_value; 353 $y_value = $temp; 354 355 $x_negative = !$x_negative; 356 357 $x_size = count($x_value); 358 $y_size = count($y_value); 359 } 360 361 // at this point, $x_value should be at least as big as - if not bigger than - $y_value 362 363 $carry = 0; 364 for ($i = 0, $j = 1; $j < $y_size; $i += 2, $j += 2) { 365 $sum = ($x_value[$j] - $y_value[$j]) * static::BASE_FULL + $x_value[$i] - $y_value[$i] - $carry; 366 367 $carry = $sum < 0; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1 368 $sum = $carry ? $sum + static::MAX_DIGIT2 : $sum; 369 370 $temp = static::BASE === 26 ? intval($sum / 0x4000000) : ($sum >> 31); 371 372 $x_value[$i] = (int)($sum - static::BASE_FULL * $temp); 373 $x_value[$j] = $temp; 374 } 375 376 if ($j == $y_size) { // ie. if $y_size is odd 377 $sum = $x_value[$i] - $y_value[$i] - $carry; 378 $carry = $sum < 0; 379 $x_value[$i] = $carry ? $sum + static::BASE_FULL : $sum; 380 ++$i; 381 } 382 383 if ($carry) { 384 for (; !$x_value[$i]; ++$i) { 385 $x_value[$i] = static::MAX_DIGIT; 386 } 387 --$x_value[$i]; 388 } 389 390 return [ 391 self::VALUE => self::trim($x_value), 392 self::SIGN => $x_negative 393 ]; 394 } 395 396 /** 397 * Performs multiplication. 398 * 399 * @param array $x_value 400 * @param bool $x_negative 401 * @param array $y_value 402 * @param bool $y_negative 403 * @return array 404 */ 405 protected static function multiplyHelper(array $x_value, $x_negative, array $y_value, $y_negative) 406 { 407 //if ( $x_value == $y_value ) { 408 // return [ 409 // self::VALUE => self::square($x_value), 410 // self::SIGN => $x_sign != $y_value 411 // ]; 412 //} 413 414 $x_length = count($x_value); 415 $y_length = count($y_value); 416 417 if (!$x_length || !$y_length) { // a 0 is being multiplied 418 return [ 419 self::VALUE => [], 420 self::SIGN => false 421 ]; 422 } 423 424 return [ 425 self::VALUE => min($x_length, $y_length) < 2 * self::KARATSUBA_CUTOFF ? 426 self::trim(self::regularMultiply($x_value, $y_value)) : 427 self::trim(self::karatsuba($x_value, $y_value)), 428 self::SIGN => $x_negative != $y_negative 429 ]; 430 } 431 432 /** 433 * Performs Karatsuba multiplication on two BigIntegers 434 * 435 * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and 436 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=120 MPM 5.2.3}. 437 * 438 * @param array $x_value 439 * @param array $y_value 440 * @return array 441 */ 442 private static function karatsuba(array $x_value, array $y_value) 443 { 444 $m = min(count($x_value) >> 1, count($y_value) >> 1); 445 446 if ($m < self::KARATSUBA_CUTOFF) { 447 return self::regularMultiply($x_value, $y_value); 448 } 449 450 $x1 = array_slice($x_value, $m); 451 $x0 = array_slice($x_value, 0, $m); 452 $y1 = array_slice($y_value, $m); 453 $y0 = array_slice($y_value, 0, $m); 454 455 $z2 = self::karatsuba($x1, $y1); 456 $z0 = self::karatsuba($x0, $y0); 457 458 $z1 = self::addHelper($x1, false, $x0, false); 459 $temp = self::addHelper($y1, false, $y0, false); 460 $z1 = self::karatsuba($z1[self::VALUE], $temp[self::VALUE]); 461 $temp = self::addHelper($z2, false, $z0, false); 462 $z1 = self::subtractHelper($z1, false, $temp[self::VALUE], false); 463 464 $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2); 465 $z1[self::VALUE] = array_merge(array_fill(0, $m, 0), $z1[self::VALUE]); 466 467 $xy = self::addHelper($z2, false, $z1[self::VALUE], $z1[self::SIGN]); 468 $xy = self::addHelper($xy[self::VALUE], $xy[self::SIGN], $z0, false); 469 470 return $xy[self::VALUE]; 471 } 472 473 /** 474 * Performs long multiplication on two BigIntegers 475 * 476 * Modeled after 'multiply' in MutableBigInteger.java. 477 * 478 * @param array $x_value 479 * @param array $y_value 480 * @return array 481 */ 482 protected static function regularMultiply(array $x_value, array $y_value) 483 { 484 $x_length = count($x_value); 485 $y_length = count($y_value); 486 487 if (!$x_length || !$y_length) { // a 0 is being multiplied 488 return []; 489 } 490 491 $product_value = self::array_repeat(0, $x_length + $y_length); 492 493 // the following for loop could be removed if the for loop following it 494 // (the one with nested for loops) initially set $i to 0, but 495 // doing so would also make the result in one set of unnecessary adds, 496 // since on the outermost loops first pass, $product->value[$k] is going 497 // to always be 0 498 499 $carry = 0; 500 for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0 501 $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0 502 $carry = static::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31); 503 $product_value[$j] = (int)($temp - static::BASE_FULL * $carry); 504 } 505 506 $product_value[$j] = $carry; 507 508 // the above for loop is what the previous comment was talking about. the 509 // following for loop is the "one with nested for loops" 510 for ($i = 1; $i < $y_length; ++$i) { 511 $carry = 0; 512 513 for ($j = 0, $k = $i; $j < $x_length; ++$j, ++$k) { 514 $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry; 515 $carry = static::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31); 516 $product_value[$k] = (int)($temp - static::BASE_FULL * $carry); 517 } 518 519 $product_value[$k] = $carry; 520 } 521 522 return $product_value; 523 } 524 525 /** 526 * Divides two BigIntegers. 527 * 528 * Returns an array whose first element contains the quotient and whose second element contains the 529 * "common residue". If the remainder would be positive, the "common residue" and the remainder are the 530 * same. If the remainder would be negative, the "common residue" is equal to the sum of the remainder 531 * and the divisor (basically, the "common residue" is the first positive modulo). 532 * 533 * @return array{static, static} 534 * @internal This function is based off of 535 * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=9 HAC 14.20}. 536 */ 537 protected function divideHelper(PHP $y) 538 { 539 if (count($y->value) == 1) { 540 list($q, $r) = $this->divide_digit($this->value, $y->value[0]); 541 $quotient = new static(); 542 $remainder = new static(); 543 $quotient->value = $q; 544 $remainder->value = [$r]; 545 $quotient->is_negative = $this->is_negative != $y->is_negative; 546 return [$this->normalize($quotient), $this->normalize($remainder)]; 547 } 548 549 $x = clone $this; 550 $y = clone $y; 551 552 $x_sign = $x->is_negative; 553 $y_sign = $y->is_negative; 554 555 $x->is_negative = $y->is_negative = false; 556 557 $diff = $x->compare($y); 558 559 if (!$diff) { 560 $temp = new static(); 561 $temp->value = [1]; 562 $temp->is_negative = $x_sign != $y_sign; 563 return [$this->normalize($temp), $this->normalize(static::$zero[static::class])]; 564 } 565 566 if ($diff < 0) { 567 // if $x is negative, "add" $y. 568 if ($x_sign) { 569 $x = $y->subtract($x); 570 } 571 return [$this->normalize(static::$zero[static::class]), $this->normalize($x)]; 572 } 573 574 // normalize $x and $y as described in HAC 14.23 / 14.24 575 $msb = $y->value[count($y->value) - 1]; 576 for ($shift = 0; !($msb & static::MSB); ++$shift) { 577 $msb <<= 1; 578 } 579 $x->lshift($shift); 580 $y->lshift($shift); 581 $y_value = &$y->value; 582 583 $x_max = count($x->value) - 1; 584 $y_max = count($y->value) - 1; 585 586 $quotient = new static(); 587 $quotient_value = &$quotient->value; 588 $quotient_value = self::array_repeat(0, $x_max - $y_max + 1); 589 590 static $temp, $lhs, $rhs; 591 if (!isset($temp)) { 592 $temp = new static(); 593 $lhs = new static(); 594 $rhs = new static(); 595 } 596 if (static::class != get_class($temp)) { 597 $temp = new static(); 598 $lhs = new static(); 599 $rhs = new static(); 600 } 601 $temp_value = &$temp->value; 602 $rhs_value = &$rhs->value; 603 604 // $temp = $y << ($x_max - $y_max-1) in base 2**26 605 $temp_value = array_merge(self::array_repeat(0, $x_max - $y_max), $y_value); 606 607 while ($x->compare($temp) >= 0) { 608 // calculate the "common residue" 609 ++$quotient_value[$x_max - $y_max]; 610 $x = $x->subtract($temp); 611 $x_max = count($x->value) - 1; 612 } 613 614 for ($i = $x_max; $i >= $y_max + 1; --$i) { 615 $x_value = &$x->value; 616 $x_window = [ 617 isset($x_value[$i]) ? $x_value[$i] : 0, 618 isset($x_value[$i - 1]) ? $x_value[$i - 1] : 0, 619 isset($x_value[$i - 2]) ? $x_value[$i - 2] : 0 620 ]; 621 $y_window = [ 622 $y_value[$y_max], 623 ($y_max > 0) ? $y_value[$y_max - 1] : 0 624 ]; 625 626 $q_index = $i - $y_max - 1; 627 if ($x_window[0] == $y_window[0]) { 628 $quotient_value[$q_index] = static::MAX_DIGIT; 629 } else { 630 $quotient_value[$q_index] = self::safe_divide( 631 $x_window[0] * static::BASE_FULL + $x_window[1], 632 $y_window[0] 633 ); 634 } 635 636 $temp_value = [$y_window[1], $y_window[0]]; 637 638 $lhs->value = [$quotient_value[$q_index]]; 639 $lhs = $lhs->multiply($temp); 640 641 $rhs_value = [$x_window[2], $x_window[1], $x_window[0]]; 642 643 while ($lhs->compare($rhs) > 0) { 644 --$quotient_value[$q_index]; 645 646 $lhs->value = [$quotient_value[$q_index]]; 647 $lhs = $lhs->multiply($temp); 648 } 649 650 $adjust = self::array_repeat(0, $q_index); 651 $temp_value = [$quotient_value[$q_index]]; 652 $temp = $temp->multiply($y); 653 $temp_value = &$temp->value; 654 if (count($temp_value)) { 655 $temp_value = array_merge($adjust, $temp_value); 656 } 657 658 $x = $x->subtract($temp); 659 660 if ($x->compare(static::$zero[static::class]) < 0) { 661 $temp_value = array_merge($adjust, $y_value); 662 $x = $x->add($temp); 663 664 --$quotient_value[$q_index]; 665 } 666 667 $x_max = count($x_value) - 1; 668 } 669 670 // unnormalize the remainder 671 $x->rshift($shift); 672 673 $quotient->is_negative = $x_sign != $y_sign; 674 675 // calculate the "common residue", if appropriate 676 if ($x_sign) { 677 $y->rshift($shift); 678 $x = $y->subtract($x); 679 } 680 681 return [$this->normalize($quotient), $this->normalize($x)]; 682 } 683 684 /** 685 * Divides a BigInteger by a regular integer 686 * 687 * abc / x = a00 / x + b0 / x + c / x 688 * 689 * @param array $dividend 690 * @param int $divisor 691 * @return array 692 */ 693 private static function divide_digit(array $dividend, $divisor) 694 { 695 $carry = 0; 696 $result = []; 697 698 for ($i = count($dividend) - 1; $i >= 0; --$i) { 699 $temp = static::BASE_FULL * $carry + $dividend[$i]; 700 $result[$i] = self::safe_divide($temp, $divisor); 701 $carry = (int)($temp - $divisor * $result[$i]); 702 } 703 704 return [$result, $carry]; 705 } 706 707 /** 708 * Single digit division 709 * 710 * Even if int64 is being used the division operator will return a float64 value 711 * if the dividend is not evenly divisible by the divisor. Since a float64 doesn't 712 * have the precision of int64 this is a problem so, when int64 is being used, 713 * we'll guarantee that the dividend is divisible by first subtracting the remainder. 714 * 715 * @param int $x 716 * @param int $y 717 * @return int 718 */ 719 private static function safe_divide($x, $y) 720 { 721 if (static::BASE === 26) { 722 return (int)($x / $y); 723 } 724 725 // static::BASE === 31 726 /** @var int */ 727 return ($x - ($x % $y)) / $y; 728 } 729 730 /** 731 * Convert an array / boolean to a PHP BigInteger object 732 * 733 * @param array $arr 734 * @return static 735 */ 736 protected function convertToObj(array $arr) 737 { 738 $result = new static(); 739 $result->value = $arr[self::VALUE]; 740 $result->is_negative = $arr[self::SIGN]; 741 742 return $this->normalize($result); 743 } 744 745 /** 746 * Normalize 747 * 748 * Removes leading zeros and truncates (if necessary) to maintain the appropriate precision 749 * 750 * @param PHP $result 751 * @return static 752 */ 753 protected function normalize(PHP $result) 754 { 755 $result->precision = $this->precision; 756 $result->bitmask = $this->bitmask; 757 758 $value = &$result->value; 759 760 if (!count($value)) { 761 $result->is_negative = false; 762 return $result; 763 } 764 765 $value = static::trim($value); 766 767 if (!empty($result->bitmask->value)) { 768 $length = min(count($value), count($result->bitmask->value)); 769 $value = array_slice($value, 0, $length); 770 771 for ($i = 0; $i < $length; ++$i) { 772 $value[$i] = $value[$i] & $result->bitmask->value[$i]; 773 } 774 775 $value = static::trim($value); 776 } 777 778 return $result; 779 } 780 781 /** 782 * Compares two numbers. 783 * 784 * @param array $x_value 785 * @param bool $x_negative 786 * @param array $y_value 787 * @param bool $y_negative 788 * @return int 789 * @see static::compare() 790 */ 791 protected static function compareHelper(array $x_value, $x_negative, array $y_value, $y_negative) 792 { 793 if ($x_negative != $y_negative) { 794 return (!$x_negative && $y_negative) ? 1 : -1; 795 } 796 797 $result = $x_negative ? -1 : 1; 798 799 if (count($x_value) != count($y_value)) { 800 return (count($x_value) > count($y_value)) ? $result : -$result; 801 } 802 $size = max(count($x_value), count($y_value)); 803 804 $x_value = array_pad($x_value, $size, 0); 805 $y_value = array_pad($y_value, $size, 0); 806 807 for ($i = count($x_value) - 1; $i >= 0; --$i) { 808 if ($x_value[$i] != $y_value[$i]) { 809 return ($x_value[$i] > $y_value[$i]) ? $result : -$result; 810 } 811 } 812 813 return 0; 814 } 815 816 /** 817 * Absolute value. 818 * 819 * @return PHP 820 */ 821 public function abs() 822 { 823 $temp = new static(); 824 $temp->value = $this->value; 825 826 return $temp; 827 } 828 829 /** 830 * Trim 831 * 832 * Removes leading zeros 833 * 834 * @param list<static> $value 835 * @return list<static> 836 */ 837 protected static function trim(array $value) 838 { 839 for ($i = count($value) - 1; $i >= 0; --$i) { 840 if ($value[$i]) { 841 break; 842 } 843 unset($value[$i]); 844 } 845 846 return $value; 847 } 848 849 /** 850 * Logical Right Shift 851 * 852 * Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift. 853 * 854 * @param int $shift 855 * @return PHP 856 */ 857 public function bitwise_rightShift($shift) 858 { 859 $temp = new static(); 860 861 // could just replace lshift with this, but then all lshift() calls would need to be rewritten 862 // and I don't want to do that... 863 $temp->value = $this->value; 864 $temp->rshift($shift); 865 866 return $this->normalize($temp); 867 } 868 869 /** 870 * Logical Left Shift 871 * 872 * Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift. 873 * 874 * @param int $shift 875 * @return PHP 876 */ 877 public function bitwise_leftShift($shift) 878 { 879 $temp = new static(); 880 // could just replace _rshift with this, but then all _lshift() calls would need to be rewritten 881 // and I don't want to do that... 882 $temp->value = $this->value; 883 $temp->lshift($shift); 884 885 return $this->normalize($temp); 886 } 887 888 /** 889 * Converts 32-bit integers to bytes. 890 * 891 * @param int $x 892 * @return string 893 */ 894 private static function int2bytes($x) 895 { 896 return ltrim(pack('N', $x), chr(0)); 897 } 898 899 /** 900 * Array Repeat 901 * 902 * @param int $input 903 * @param int $multiplier 904 * @return array 905 */ 906 protected static function array_repeat($input, $multiplier) 907 { 908 return $multiplier ? array_fill(0, $multiplier, $input) : []; 909 } 910 911 /** 912 * Logical Left Shift 913 * 914 * Shifts BigInteger's by $shift bits. 915 * 916 * @param int $shift 917 */ 918 protected function lshift($shift) 919 { 920 if ($shift == 0) { 921 return; 922 } 923 924 $num_digits = (int)($shift / static::BASE); 925 $shift %= static::BASE; 926 $shift = 1 << $shift; 927 928 $carry = 0; 929 930 for ($i = 0; $i < count($this->value); ++$i) { 931 $temp = $this->value[$i] * $shift + $carry; 932 $carry = static::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31); 933 $this->value[$i] = (int)($temp - $carry * static::BASE_FULL); 934 } 935 936 if ($carry) { 937 $this->value[count($this->value)] = $carry; 938 } 939 940 while ($num_digits--) { 941 array_unshift($this->value, 0); 942 } 943 } 944 945 /** 946 * Logical Right Shift 947 * 948 * Shifts BigInteger's by $shift bits. 949 * 950 * @param int $shift 951 */ 952 protected function rshift($shift) 953 { 954 if ($shift == 0) { 955 return; 956 } 957 958 $num_digits = (int)($shift / static::BASE); 959 $shift %= static::BASE; 960 $carry_shift = static::BASE - $shift; 961 $carry_mask = (1 << $shift) - 1; 962 963 if ($num_digits) { 964 $this->value = array_slice($this->value, $num_digits); 965 } 966 967 $carry = 0; 968 969 for ($i = count($this->value) - 1; $i >= 0; --$i) { 970 $temp = $this->value[$i] >> $shift | $carry; 971 $carry = ($this->value[$i] & $carry_mask) << $carry_shift; 972 $this->value[$i] = $temp; 973 } 974 975 $this->value = static::trim($this->value); 976 } 977 978 /** 979 * Performs modular exponentiation. 980 * 981 * @param PHP $e 982 * @param PHP $n 983 * @return PHP 984 */ 985 protected function powModInner(PHP $e, PHP $n) 986 { 987 try { 988 $class = static::$modexpEngine[static::class]; 989 return $class::powModHelper($this, $e, $n, static::class); 990 } catch (\Exception $err) { 991 return PHP\DefaultEngine::powModHelper($this, $e, $n, static::class); 992 } 993 } 994 995 /** 996 * Performs squaring 997 * 998 * @param list<static> $x 999 * @return list<static> 1000 */ 1001 protected static function square(array $x) 1002 { 1003 return count($x) < 2 * self::KARATSUBA_CUTOFF ? 1004 self::trim(self::baseSquare($x)) : 1005 self::trim(self::karatsubaSquare($x)); 1006 } 1007 1008 /** 1009 * Performs traditional squaring on two BigIntegers 1010 * 1011 * Squaring can be done faster than multiplying a number by itself can be. See 1012 * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=7 HAC 14.2.4} / 1013 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=141 MPM 5.3} for more information. 1014 * 1015 * @param array $value 1016 * @return array 1017 */ 1018 protected static function baseSquare(array $value) 1019 { 1020 if (empty($value)) { 1021 return []; 1022 } 1023 $square_value = self::array_repeat(0, 2 * count($value)); 1024 1025 for ($i = 0, $max_index = count($value) - 1; $i <= $max_index; ++$i) { 1026 $i2 = $i << 1; 1027 1028 $temp = $square_value[$i2] + $value[$i] * $value[$i]; 1029 $carry = static::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31); 1030 $square_value[$i2] = (int)($temp - static::BASE_FULL * $carry); 1031 1032 // note how we start from $i+1 instead of 0 as we do in multiplication. 1033 for ($j = $i + 1, $k = $i2 + 1; $j <= $max_index; ++$j, ++$k) { 1034 $temp = $square_value[$k] + 2 * $value[$j] * $value[$i] + $carry; 1035 $carry = static::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31); 1036 $square_value[$k] = (int)($temp - static::BASE_FULL * $carry); 1037 } 1038 1039 // the following line can yield values larger 2**15. at this point, PHP should switch 1040 // over to floats. 1041 $square_value[$i + $max_index + 1] = $carry; 1042 } 1043 1044 return $square_value; 1045 } 1046 1047 /** 1048 * Performs Karatsuba "squaring" on two BigIntegers 1049 * 1050 * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and 1051 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=151 MPM 5.3.4}. 1052 * 1053 * @param array $value 1054 * @return array 1055 */ 1056 protected static function karatsubaSquare(array $value) 1057 { 1058 $m = count($value) >> 1; 1059 1060 if ($m < self::KARATSUBA_CUTOFF) { 1061 return self::baseSquare($value); 1062 } 1063 1064 $x1 = array_slice($value, $m); 1065 $x0 = array_slice($value, 0, $m); 1066 1067 $z2 = self::karatsubaSquare($x1); 1068 $z0 = self::karatsubaSquare($x0); 1069 1070 $z1 = self::addHelper($x1, false, $x0, false); 1071 $z1 = self::karatsubaSquare($z1[self::VALUE]); 1072 $temp = self::addHelper($z2, false, $z0, false); 1073 $z1 = self::subtractHelper($z1, false, $temp[self::VALUE], false); 1074 1075 $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2); 1076 $z1[self::VALUE] = array_merge(array_fill(0, $m, 0), $z1[self::VALUE]); 1077 1078 $xx = self::addHelper($z2, false, $z1[self::VALUE], $z1[self::SIGN]); 1079 $xx = self::addHelper($xx[self::VALUE], $xx[self::SIGN], $z0, false); 1080 1081 return $xx[self::VALUE]; 1082 } 1083 1084 /** 1085 * Make the current number odd 1086 * 1087 * If the current number is odd it'll be unchanged. If it's even, one will be added to it. 1088 * 1089 * @see self::randomPrime() 1090 */ 1091 protected function make_odd() 1092 { 1093 $this->value[0] |= 1; 1094 } 1095 1096 /** 1097 * Test the number against small primes. 1098 * 1099 * @see self::isPrime() 1100 */ 1101 protected function testSmallPrimes() 1102 { 1103 if ($this->value == [1]) { 1104 return false; 1105 } 1106 if ($this->value == [2]) { 1107 return true; 1108 } 1109 if (~$this->value[0] & 1) { 1110 return false; 1111 } 1112 1113 $value = $this->value; 1114 foreach (static::PRIMES as $prime) { 1115 list(, $r) = self::divide_digit($value, $prime); 1116 if (!$r) { 1117 return count($value) == 1 && $value[0] == $prime; 1118 } 1119 } 1120 1121 return true; 1122 } 1123 1124 /** 1125 * Scan for 1 and right shift by that amount 1126 * 1127 * ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s)); 1128 * 1129 * @param PHP $r 1130 * @return int 1131 * @see self::isPrime() 1132 */ 1133 public static function scan1divide(PHP $r) 1134 { 1135 $r_value = &$r->value; 1136 for ($i = 0, $r_length = count($r_value); $i < $r_length; ++$i) { 1137 $temp = ~$r_value[$i] & static::MAX_DIGIT; 1138 for ($j = 1; ($temp >> $j) & 1; ++$j) { 1139 } 1140 if ($j <= static::BASE) { 1141 break; 1142 } 1143 } 1144 $s = static::BASE * $i + $j; 1145 $r->rshift($s); 1146 return $s; 1147 } 1148 1149 /** 1150 * Performs exponentiation. 1151 * 1152 * @param PHP $n 1153 * @return PHP 1154 */ 1155 protected function powHelper(PHP $n) 1156 { 1157 if ($n->compare(static::$zero[static::class]) == 0) { 1158 return new static(1); 1159 } // n^0 = 1 1160 1161 $temp = clone $this; 1162 while (!$n->equals(static::$one[static::class])) { 1163 $temp = $temp->multiply($this); 1164 $n = $n->subtract(static::$one[static::class]); 1165 } 1166 1167 return $temp; 1168 } 1169 1170 /** 1171 * Is Odd? 1172 * 1173 * @return bool 1174 */ 1175 public function isOdd() 1176 { 1177 return (bool)($this->value[0] & 1); 1178 } 1179 1180 /** 1181 * Tests if a bit is set 1182 * 1183 * @return bool 1184 */ 1185 public function testBit($x) 1186 { 1187 $digit = (int) floor($x / static::BASE); 1188 $bit = $x % static::BASE; 1189 1190 if (!isset($this->value[$digit])) { 1191 return false; 1192 } 1193 1194 return (bool)($this->value[$digit] & (1 << $bit)); 1195 } 1196 1197 /** 1198 * Is Negative? 1199 * 1200 * @return bool 1201 */ 1202 public function isNegative() 1203 { 1204 return $this->is_negative; 1205 } 1206 1207 /** 1208 * Negate 1209 * 1210 * Given $k, returns -$k 1211 * 1212 * @return static 1213 */ 1214 public function negate() 1215 { 1216 $temp = clone $this; 1217 $temp->is_negative = !$temp->is_negative; 1218 1219 return $temp; 1220 } 1221 1222 /** 1223 * Bitwise Split 1224 * 1225 * Splits BigInteger's into chunks of $split bits 1226 * 1227 * @param int $split 1228 * @return list<static> 1229 */ 1230 public function bitwise_split($split) 1231 { 1232 if ($split < 1) { 1233 throw new \RuntimeException('Offset must be greater than 1'); 1234 } 1235 1236 $width = (int)($split / static::BASE); 1237 if (!$width) { 1238 $arr = $this->bitwise_small_split($split); 1239 return array_map(function ($digit) { 1240 $temp = new static(); 1241 $temp->value = $digit != 0 ? [$digit] : []; 1242 return $temp; 1243 }, $arr); 1244 } 1245 1246 $vals = []; 1247 $val = $this->value; 1248 1249 $i = $overflow = 0; 1250 $len = count($val); 1251 while ($i < $len) { 1252 $digit = []; 1253 if (!$overflow) { 1254 $digit = array_slice($val, $i, $width); 1255 $i += $width; 1256 $overflow = $split % static::BASE; 1257 if ($overflow) { 1258 $mask = (1 << $overflow) - 1; 1259 $temp = isset($val[$i]) ? $val[$i] : 0; 1260 $digit[] = $temp & $mask; 1261 } 1262 } else { 1263 $remaining = static::BASE - $overflow; 1264 $tempsplit = $split - $remaining; 1265 $tempwidth = (int)($tempsplit / static::BASE + 1); 1266 $digit = array_slice($val, $i, $tempwidth); 1267 $i += $tempwidth; 1268 $tempoverflow = $tempsplit % static::BASE; 1269 if ($tempoverflow) { 1270 $tempmask = (1 << $tempoverflow) - 1; 1271 $temp = isset($val[$i]) ? $val[$i] : 0; 1272 $digit[] = $temp & $tempmask; 1273 } 1274 $newbits = 0; 1275 for ($j = count($digit) - 1; $j >= 0; $j--) { 1276 $temp = $digit[$j] & $mask; 1277 $digit[$j] = ($digit[$j] >> $overflow) | ($newbits << $remaining); 1278 $newbits = $temp; 1279 } 1280 $overflow = $tempoverflow; 1281 $mask = $tempmask; 1282 } 1283 $temp = new static(); 1284 $temp->value = static::trim($digit); 1285 $vals[] = $temp; 1286 } 1287 1288 return array_reverse($vals); 1289 } 1290 1291 /** 1292 * Bitwise Split where $split < static::BASE 1293 * 1294 * @param int $split 1295 * @return list<int> 1296 */ 1297 private function bitwise_small_split($split) 1298 { 1299 $vals = []; 1300 $val = $this->value; 1301 1302 $mask = (1 << $split) - 1; 1303 1304 $i = $overflow = 0; 1305 $len = count($val); 1306 $val[] = 0; 1307 $remaining = static::BASE; 1308 while ($i != $len) { 1309 $digit = $val[$i] & $mask; 1310 $val[$i] >>= $split; 1311 if (!$overflow) { 1312 $remaining -= $split; 1313 $overflow = $split <= $remaining ? 0 : $split - $remaining; 1314 1315 if (!$remaining) { 1316 $i++; 1317 $remaining = static::BASE; 1318 $overflow = 0; 1319 } 1320 } elseif (++$i != $len) { 1321 $tempmask = (1 << $overflow) - 1; 1322 $digit |= ($val[$i] & $tempmask) << $remaining; 1323 $val[$i] >>= $overflow; 1324 $remaining = static::BASE - $overflow; 1325 $overflow = $split <= $remaining ? 0 : $split - $remaining; 1326 } 1327 1328 $vals[] = $digit; 1329 } 1330 1331 while ($vals[count($vals) - 1] == 0) { 1332 unset($vals[count($vals) - 1]); 1333 } 1334 1335 return array_reverse($vals); 1336 } 1337 }
title
Description
Body
title
Description
Body
title
Description
Body
title
Body
| Generated: Wed Sep 7 05:41:13 2022 | Chilli.vc Blog - For Webmaster,Blog-Writer,System Admin and Domainer |