[Summary view] [Print] [Text view]

   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 <[email protected]>
  26   * @copyright 2017 Jim Wigginton
  27   * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
  28   */
  29  
  30  namespace phpseclib3\Math;
  31  
  32  use phpseclib3\Exception\BadConfigurationException;
  33  use 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 <[email protected]>
  41   * @access  public
  42   */
  43  class 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  }