1<?php 2 3/** 4 * Pure-PHP arbitrary precision integer arithmetic library. 5 * 6 * Supports base-2, base-10, base-16, and base-256 numbers. Uses the GMP or BCMath extensions, if available, 7 * and an internal implementation, otherwise. 8 * 9 * PHP version 5 and 7 10 * 11 * Here's an example of how to use this library: 12 * <code> 13 * <?php 14 * $a = new \phpseclib3\Math\BigInteger(2); 15 * $b = new \phpseclib3\Math\BigInteger(3); 16 * 17 * $c = $a->add($b); 18 * 19 * echo $c->toString(); // outputs 5 20 * ?> 21 * </code> 22 * 23 * @category Math 24 * @package BigInteger 25 * @author Jim Wigginton <terrafrost@php.net> 26 * @copyright 2017 Jim Wigginton 27 * @license http://www.opensource.org/licenses/mit-license.html MIT License 28 */ 29 30namespace phpseclib3\Math; 31 32use phpseclib3\Exception\BadConfigurationException; 33use phpseclib3\Math\BigInteger\Engines\Engine; 34 35/** 36 * Pure-PHP arbitrary precision integer arithmetic library. Supports base-2, base-10, base-16, and base-256 37 * numbers. 38 * 39 * @package BigInteger 40 * @author Jim Wigginton <terrafrost@php.net> 41 * @access public 42 */ 43class BigInteger implements \JsonSerializable 44{ 45 /** 46 * Main Engine 47 * 48 * @var class-string<Engine> 49 */ 50 private static $mainEngine; 51 52 /** 53 * Selected Engines 54 * 55 * @var list<string> 56 */ 57 private static $engines; 58 59 /** 60 * The actual BigInteger object 61 * 62 * @var object 63 */ 64 private $value; 65 66 /** 67 * Mode independent value used for serialization. 68 * 69 * @see self::__sleep() 70 * @see self::__wakeup() 71 * @var string 72 */ 73 private $hex; 74 75 /** 76 * Precision (used only for serialization) 77 * 78 * @see self::__sleep() 79 * @see self::__wakeup() 80 * @var int 81 */ 82 private $precision; 83 84 /** 85 * Sets engine type. 86 * 87 * Throws an exception if the type is invalid 88 * 89 * @param string $main 90 * @param list<string> $modexps optional 91 * @return void 92 */ 93 public static function setEngine($main, array $modexps = ['DefaultEngine']) 94 { 95 self::$engines = []; 96 97 $fqmain = 'phpseclib3\\Math\\BigInteger\\Engines\\' . $main; 98 if (!class_exists($fqmain) || !method_exists($fqmain, 'isValidEngine')) { 99 throw new \InvalidArgumentException("$main is not a valid engine"); 100 } 101 if (!$fqmain::isValidEngine()) { 102 throw new BadConfigurationException("$main is not setup correctly on this system"); 103 } 104 /** @var class-string<Engine> $fqmain */ 105 self::$mainEngine = $fqmain; 106 107 if (!in_array('Default', $modexps)) { 108 $modexps[] = 'DefaultEngine'; 109 } 110 111 $found = false; 112 foreach ($modexps as $modexp) { 113 try { 114 $fqmain::setModExpEngine($modexp); 115 $found = true; 116 break; 117 } catch (\Exception $e) { 118 } 119 } 120 121 if (!$found) { 122 throw new BadConfigurationException("No valid modular exponentiation engine found for $main"); 123 } 124 125 self::$engines = [$main, $modexp]; 126 } 127 128 /** 129 * Returns the engine type 130 * 131 * @return string[] 132 */ 133 public static function getEngine() 134 { 135 self::initialize_static_variables(); 136 137 return self::$engines; 138 } 139 140 /** 141 * Initialize static variables 142 */ 143 private static function initialize_static_variables() 144 { 145 if (!isset(self::$mainEngine)) { 146 $engines = [ 147 ['GMP'], 148 ['PHP64', ['OpenSSL']], 149 ['BCMath', ['OpenSSL']], 150 ['PHP32', ['OpenSSL']] 151 ]; 152 foreach ($engines as $engine) { 153 try { 154 self::setEngine($engine[0], isset($engine[1]) ? $engine[1] : []); 155 break; 156 } catch (\Exception $e) { 157 } 158 } 159 } 160 } 161 162 /** 163 * Converts base-2, base-10, base-16, and binary strings (base-256) to BigIntegers. 164 * 165 * If the second parameter - $base - is negative, then it will be assumed that the number's are encoded using 166 * two's compliment. The sole exception to this is -10, which is treated the same as 10 is. 167 * 168 * @param string|int|BigInteger\Engines\Engine $x Base-10 number or base-$base number if $base set. 169 * @param int $base 170 */ 171 public function __construct($x = 0, $base = 10) 172 { 173 self::initialize_static_variables(); 174 175 if ($x instanceof self::$mainEngine) { 176 $this->value = clone $x; 177 } elseif ($x instanceof BigInteger\Engines\Engine) { 178 $this->value = new static("$x"); 179 $this->value->setPrecision($x->getPrecision()); 180 } else { 181 $this->value = new self::$mainEngine($x, $base); 182 } 183 } 184 185 /** 186 * Converts a BigInteger to a base-10 number. 187 * 188 * @return string 189 */ 190 public function toString() 191 { 192 return $this->value->toString(); 193 } 194 195 /** 196 * __toString() magic method 197 */ 198 public function __toString() 199 { 200 return (string)$this->value; 201 } 202 203 /** 204 * __debugInfo() magic method 205 * 206 * Will be called, automatically, when print_r() or var_dump() are called 207 */ 208 public function __debugInfo() 209 { 210 return $this->value->__debugInfo(); 211 } 212 213 /** 214 * Converts a BigInteger to a byte string (eg. base-256). 215 * 216 * @param bool $twos_compliment 217 * @return string 218 */ 219 public function toBytes($twos_compliment = false) 220 { 221 return $this->value->toBytes($twos_compliment); 222 } 223 224 /** 225 * Converts a BigInteger to a hex string (eg. base-16). 226 * 227 * @param bool $twos_compliment 228 * @return string 229 */ 230 public function toHex($twos_compliment = false) 231 { 232 return $this->value->toHex($twos_compliment); 233 } 234 235 /** 236 * Converts a BigInteger to a bit string (eg. base-2). 237 * 238 * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're 239 * saved as two's compliment. 240 * 241 * @param bool $twos_compliment 242 * @return string 243 */ 244 public function toBits($twos_compliment = false) 245 { 246 return $this->value->toBits($twos_compliment); 247 } 248 249 /** 250 * Adds two BigIntegers. 251 * 252 * @param BigInteger $y 253 * @return BigInteger 254 */ 255 public function add(BigInteger $y) 256 { 257 return new static($this->value->add($y->value)); 258 } 259 260 /** 261 * Subtracts two BigIntegers. 262 * 263 * @param BigInteger $y 264 * @return BigInteger 265 */ 266 public function subtract(BigInteger $y) 267 { 268 return new static($this->value->subtract($y->value)); 269 } 270 271 /** 272 * Multiplies two BigIntegers 273 * 274 * @param BigInteger $x 275 * @return BigInteger 276 */ 277 public function multiply(BigInteger $x) 278 { 279 return new static($this->value->multiply($x->value)); 280 } 281 282 /** 283 * Divides two BigIntegers. 284 * 285 * Returns an array whose first element contains the quotient and whose second element contains the 286 * "common residue". If the remainder would be positive, the "common residue" and the remainder are the 287 * same. If the remainder would be negative, the "common residue" is equal to the sum of the remainder 288 * and the divisor (basically, the "common residue" is the first positive modulo). 289 * 290 * Here's an example: 291 * <code> 292 * <?php 293 * $a = new \phpseclib3\Math\BigInteger('10'); 294 * $b = new \phpseclib3\Math\BigInteger('20'); 295 * 296 * list($quotient, $remainder) = $a->divide($b); 297 * 298 * echo $quotient->toString(); // outputs 0 299 * echo "\r\n"; 300 * echo $remainder->toString(); // outputs 10 301 * ?> 302 * </code> 303 * 304 * @param BigInteger $y 305 * @return BigInteger[] 306 */ 307 public function divide(BigInteger $y) 308 { 309 list($q, $r) = $this->value->divide($y->value); 310 return [ 311 new static($q), 312 new static($r) 313 ]; 314 } 315 316 /** 317 * Calculates modular inverses. 318 * 319 * Say you have (30 mod 17 * x mod 17) mod 17 == 1. x can be found using modular inverses. 320 * 321 * @param BigInteger $n 322 * @return BigInteger 323 */ 324 public function modInverse(BigInteger $n) 325 { 326 return new static($this->value->modInverse($n->value)); 327 } 328 329 /** 330 * Calculates modular inverses. 331 * 332 * Say you have (30 mod 17 * x mod 17) mod 17 == 1. x can be found using modular inverses. 333 * 334 * @param BigInteger $n 335 * @return BigInteger[] 336 */ 337 public function extendedGCD(BigInteger $n) 338 { 339 extract($this->value->extendedGCD($n->value)); 340 /** 341 * @var BigInteger $gcd 342 * @var BigInteger $x 343 * @var BigInteger $y 344 */ 345 return [ 346 'gcd' => new static($gcd), 347 'x' => new static($x), 348 'y' => new static($y) 349 ]; 350 } 351 352 /** 353 * Calculates the greatest common divisor 354 * 355 * Say you have 693 and 609. The GCD is 21. 356 * 357 * @param BigInteger $n 358 * @return BigInteger 359 */ 360 public function gcd(BigInteger $n) 361 { 362 return new static($this->value->gcd($n->value)); 363 } 364 365 /** 366 * Absolute value. 367 * 368 * @return BigInteger 369 * @access public 370 */ 371 public function abs() 372 { 373 return new static($this->value->abs()); 374 } 375 376 /** 377 * Set Precision 378 * 379 * Some bitwise operations give different results depending on the precision being used. Examples include left 380 * shift, not, and rotates. 381 * 382 * @param int $bits 383 */ 384 public function setPrecision($bits) 385 { 386 $this->value->setPrecision($bits); 387 } 388 389 /** 390 * Get Precision 391 * 392 * Returns the precision if it exists, false if it doesn't 393 * 394 * @return int|bool 395 */ 396 public function getPrecision() 397 { 398 return $this->value->getPrecision(); 399 } 400 401 /** 402 * Serialize 403 * 404 * Will be called, automatically, when serialize() is called on a BigInteger object. 405 * 406 * __sleep() / __wakeup() have been around since PHP 4.0 407 * 408 * \Serializable was introduced in PHP 5.1 and deprecated in PHP 8.1: 409 * https://wiki.php.net/rfc/phase_out_serializable 410 * 411 * __serialize() / __unserialize() were introduced in PHP 7.4: 412 * https://wiki.php.net/rfc/custom_object_serialization 413 * 414 * @return array 415 */ 416 public function __sleep() 417 { 418 $this->hex = $this->toHex(true); 419 $vars = ['hex']; 420 if ($this->getPrecision() > 0) { 421 $vars[] = 'precision'; 422 } 423 return $vars; 424 } 425 426 /** 427 * Serialize 428 * 429 * Will be called, automatically, when unserialize() is called on a BigInteger object. 430 */ 431 public function __wakeup() 432 { 433 $temp = new static($this->hex, -16); 434 $this->value = $temp->value; 435 if ($this->precision > 0) { 436 // recalculate $this->bitmask 437 $this->setPrecision($this->precision); 438 } 439 } 440 441 /** 442 * JSON Serialize 443 * 444 * Will be called, automatically, when json_encode() is called on a BigInteger object. 445 */ 446 #[\ReturnTypeWillChange] 447 public function jsonSerialize() 448 { 449 $result = ['hex' => $this->toHex(true)]; 450 if ($this->precision > 0) { 451 $result['precision'] = $this->getPrecision(); 452 } 453 return $result; 454 } 455 456 /** 457 * Performs modular exponentiation. 458 * 459 * @param BigInteger $e 460 * @param BigInteger $n 461 * @return BigInteger 462 */ 463 public function powMod(BigInteger $e, BigInteger $n) 464 { 465 return new static($this->value->powMod($e->value, $n->value)); 466 } 467 468 /** 469 * Performs modular exponentiation. 470 * 471 * @param BigInteger $e 472 * @param BigInteger $n 473 * @return BigInteger 474 */ 475 public function modPow(BigInteger $e, BigInteger $n) 476 { 477 return new static($this->value->modPow($e->value, $n->value)); 478 } 479 480 /** 481 * Compares two numbers. 482 * 483 * Although one might think !$x->compare($y) means $x != $y, it, in fact, means the opposite. The reason for this 484 * is demonstrated thusly: 485 * 486 * $x > $y: $x->compare($y) > 0 487 * $x < $y: $x->compare($y) < 0 488 * $x == $y: $x->compare($y) == 0 489 * 490 * Note how the same comparison operator is used. If you want to test for equality, use $x->equals($y). 491 * 492 * {@internal Could return $this->subtract($x), but that's not as fast as what we do do.} 493 * 494 * @param BigInteger $y 495 * @return int in case < 0 if $this is less than $y; > 0 if $this is greater than $y, and 0 if they are equal. 496 * @access public 497 * @see self::equals() 498 */ 499 public function compare(BigInteger $y) 500 { 501 return $this->value->compare($y->value); 502 } 503 504 /** 505 * Tests the equality of two numbers. 506 * 507 * If you need to see if one number is greater than or less than another number, use BigInteger::compare() 508 * 509 * @param BigInteger $x 510 * @return bool 511 */ 512 public function equals(BigInteger $x) 513 { 514 return $this->value->equals($x->value); 515 } 516 517 /** 518 * Logical Not 519 * 520 * @return BigInteger 521 */ 522 public function bitwise_not() 523 { 524 return new static($this->value->bitwise_not()); 525 } 526 527 /** 528 * Logical And 529 * 530 * @param BigInteger $x 531 * @return BigInteger 532 */ 533 public function bitwise_and(BigInteger $x) 534 { 535 return new static($this->value->bitwise_and($x->value)); 536 } 537 538 /** 539 * Logical Or 540 * 541 * @param BigInteger $x 542 * @return BigInteger 543 */ 544 public function bitwise_or(BigInteger $x) 545 { 546 return new static($this->value->bitwise_or($x->value)); 547 } 548 549 /** 550 * Logical Exclusive Or 551 * 552 * @param BigInteger $x 553 * @return BigInteger 554 */ 555 public function bitwise_xor(BigInteger $x) 556 { 557 return new static($this->value->bitwise_xor($x->value)); 558 } 559 560 /** 561 * Logical Right Shift 562 * 563 * Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift. 564 * 565 * @param int $shift 566 * @return BigInteger 567 */ 568 public function bitwise_rightShift($shift) 569 { 570 return new static($this->value->bitwise_rightShift($shift)); 571 } 572 573 /** 574 * Logical Left Shift 575 * 576 * Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift. 577 * 578 * @param int $shift 579 * @return BigInteger 580 */ 581 public function bitwise_leftShift($shift) 582 { 583 return new static($this->value->bitwise_leftShift($shift)); 584 } 585 586 /** 587 * Logical Left Rotate 588 * 589 * Instead of the top x bits being dropped they're appended to the shifted bit string. 590 * 591 * @param int $shift 592 * @return BigInteger 593 */ 594 public function bitwise_leftRotate($shift) 595 { 596 return new static($this->value->bitwise_leftRotate($shift)); 597 } 598 599 /** 600 * Logical Right Rotate 601 * 602 * Instead of the bottom x bits being dropped they're prepended to the shifted bit string. 603 * 604 * @param int $shift 605 * @return BigInteger 606 */ 607 public function bitwise_rightRotate($shift) 608 { 609 return new static($this->value->bitwise_rightRotate($shift)); 610 } 611 612 /** 613 * Returns the smallest and largest n-bit number 614 * 615 * @param int $bits 616 * @return BigInteger[] 617 */ 618 public static function minMaxBits($bits) 619 { 620 self::initialize_static_variables(); 621 622 $class = self::$mainEngine; 623 extract($class::minMaxBits($bits)); 624 /** @var BigInteger $min 625 * @var BigInteger $max 626 */ 627 return [ 628 'min' => new static($min), 629 'max' => new static($max) 630 ]; 631 } 632 633 /** 634 * Return the size of a BigInteger in bits 635 * 636 * @return int 637 */ 638 public function getLength() 639 { 640 return $this->value->getLength(); 641 } 642 643 /** 644 * Return the size of a BigInteger in bytes 645 * 646 * @return int 647 */ 648 public function getLengthInBytes() 649 { 650 return $this->value->getLengthInBytes(); 651 } 652 653 /** 654 * Generates a random number of a certain size 655 * 656 * Bit length is equal to $size 657 * 658 * @param int $size 659 * @return BigInteger 660 */ 661 public static function random($size) 662 { 663 self::initialize_static_variables(); 664 665 $class = self::$mainEngine; 666 return new static($class::random($size)); 667 } 668 669 /** 670 * Generates a random prime number of a certain size 671 * 672 * Bit length is equal to $size 673 * 674 * @param int $size 675 * @return BigInteger 676 */ 677 public static function randomPrime($size) 678 { 679 self::initialize_static_variables(); 680 681 $class = self::$mainEngine; 682 return new static($class::randomPrime($size)); 683 } 684 685 /** 686 * Generate a random prime number between a range 687 * 688 * If there's not a prime within the given range, false will be returned. 689 * 690 * @param BigInteger $min 691 * @param BigInteger $max 692 * @return false|BigInteger 693 */ 694 public static function randomRangePrime(BigInteger $min, BigInteger $max) 695 { 696 $class = self::$mainEngine; 697 return new static($class::randomRangePrime($min->value, $max->value)); 698 } 699 700 /** 701 * Generate a random number between a range 702 * 703 * Returns a random number between $min and $max where $min and $max 704 * can be defined using one of the two methods: 705 * 706 * BigInteger::randomRange($min, $max) 707 * BigInteger::randomRange($max, $min) 708 * 709 * @param BigInteger $min 710 * @param BigInteger $max 711 * @return BigInteger 712 */ 713 public static function randomRange(BigInteger $min, BigInteger $max) 714 { 715 $class = self::$mainEngine; 716 return new static($class::randomRange($min->value, $max->value)); 717 } 718 719 /** 720 * Checks a numer to see if it's prime 721 * 722 * Assuming the $t parameter is not set, this function has an error rate of 2**-80. The main motivation for the 723 * $t parameter is distributability. BigInteger::randomPrime() can be distributed across multiple pageloads 724 * on a website instead of just one. 725 * 726 * @param int|bool $t 727 * @return bool 728 */ 729 public function isPrime($t = false) 730 { 731 return $this->value->isPrime($t); 732 } 733 734 /** 735 * Calculates the nth root of a biginteger. 736 * 737 * Returns the nth root of a positive biginteger, where n defaults to 2 738 * 739 * @param int $n optional 740 * @return BigInteger 741 */ 742 public function root($n = 2) 743 { 744 return new static($this->value->root($n)); 745 } 746 747 /** 748 * Performs exponentiation. 749 * 750 * @param BigInteger $n 751 * @return BigInteger 752 */ 753 public function pow(BigInteger $n) 754 { 755 return new static($this->value->pow($n->value)); 756 } 757 758 /** 759 * Return the minimum BigInteger between an arbitrary number of BigIntegers. 760 * 761 * @param BigInteger ...$nums 762 * @return BigInteger 763 */ 764 public static function min(BigInteger ...$nums) 765 { 766 $class = self::$mainEngine; 767 $nums = array_map(function ($num) { 768 return $num->value; 769 }, $nums); 770 return new static($class::min(...$nums)); 771 } 772 773 /** 774 * Return the maximum BigInteger between an arbitrary number of BigIntegers. 775 * 776 * @param BigInteger ...$nums 777 * @return BigInteger 778 */ 779 public static function max(BigInteger ...$nums) 780 { 781 $class = self::$mainEngine; 782 $nums = array_map(function ($num) { 783 return $num->value; 784 }, $nums); 785 return new static($class::max(...$nums)); 786 } 787 788 /** 789 * Tests BigInteger to see if it is between two integers, inclusive 790 * 791 * @param BigInteger $min 792 * @param BigInteger $max 793 * @return bool 794 */ 795 public function between(BigInteger $min, BigInteger $max) 796 { 797 return $this->value->between($min->value, $max->value); 798 } 799 800 /** 801 * Clone 802 */ 803 public function __clone() 804 { 805 $this->value = clone $this->value; 806 } 807 808 /** 809 * Is Odd? 810 * 811 * @return bool 812 */ 813 public function isOdd() 814 { 815 return $this->value->isOdd(); 816 } 817 818 /** 819 * Tests if a bit is set 820 * 821 * @param int $x 822 * @return bool 823 */ 824 public function testBit($x) 825 { 826 return $this->value->testBit($x); 827 } 828 829 /** 830 * Is Negative? 831 * 832 * @return bool 833 */ 834 public function isNegative() 835 { 836 return $this->value->isNegative(); 837 } 838 839 /** 840 * Negate 841 * 842 * Given $k, returns -$k 843 * 844 * @return BigInteger 845 */ 846 public function negate() 847 { 848 return new static($this->value->negate()); 849 } 850 851 /** 852 * Scan for 1 and right shift by that amount 853 * 854 * ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s)); 855 * 856 * @param BigInteger $r 857 * @return int 858 */ 859 public static function scan1divide(BigInteger $r) 860 { 861 $class = self::$mainEngine; 862 return $class::scan1divide($r->value); 863 } 864 865 /** 866 * Create Recurring Modulo Function 867 * 868 * Sometimes it may be desirable to do repeated modulos with the same number outside of 869 * modular exponentiation 870 * 871 * @return callable 872 */ 873 public function createRecurringModuloFunction() 874 { 875 $func = $this->value->createRecurringModuloFunction(); 876 return function (BigInteger $x) use ($func) { 877 return new static($func($x->value)); 878 }; 879 } 880 881 /** 882 * Bitwise Split 883 * 884 * Splits BigInteger's into chunks of $split bits 885 * 886 * @param int $split 887 * @return BigInteger[] 888 */ 889 public function bitwise_split($split) 890 { 891 return array_map(function ($val) { 892 return new static($val); 893 }, $this->value->bitwise_split($split)); 894 } 895} 896