[Summary view] [Print] [Text view]

   1  <?php
   2  
   3  /**
   4   * BCMath BigInteger 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;
  15  
  16  use phpseclib3\Common\Functions\Strings;
  17  use phpseclib3\Exception\BadConfigurationException;
  18  
  19  /**
  20   * BCMath Engine.
  21   *
  22   * @author  Jim Wigginton <terrafrost@php.net>
  23   */
  24  class BCMath extends Engine
  25  {
  26      /**
  27       * Can Bitwise operations be done fast?
  28       *
  29       * @see parent::bitwise_leftRotate()
  30       * @see parent::bitwise_rightRotate()
  31       */
  32      const FAST_BITWISE = false;
  33  
  34      /**
  35       * Engine Directory
  36       *
  37       * @see parent::setModExpEngine
  38       */
  39      const ENGINE_DIR = 'BCMath';
  40  
  41      /**
  42       * Test for engine validity
  43       *
  44       * @return bool
  45       * @see parent::__construct()
  46       */
  47      public static function isValidEngine()
  48      {
  49          return extension_loaded('bcmath');
  50      }
  51  
  52      /**
  53       * Default constructor
  54       *
  55       * @param mixed $x integer Base-10 number or base-$base number if $base set.
  56       * @param int $base
  57       * @see parent::__construct()
  58       */
  59      public function __construct($x = 0, $base = 10)
  60      {
  61          if (!isset(static::$isValidEngine[static::class])) {
  62              static::$isValidEngine[static::class] = self::isValidEngine();
  63          }
  64          if (!static::$isValidEngine[static::class]) {
  65              throw new BadConfigurationException('BCMath is not setup correctly on this system');
  66          }
  67  
  68          $this->value = '0';
  69  
  70          parent::__construct($x, $base);
  71      }
  72  
  73      /**
  74       * Initialize a BCMath BigInteger Engine instance
  75       *
  76       * @param int $base
  77       * @see parent::__construct()
  78       */
  79      protected function initialize($base)
  80      {
  81          switch (abs($base)) {
  82              case 256:
  83                  // round $len to the nearest 4
  84                  $len = (strlen($this->value) + 3) & ~3;
  85  
  86                  $x = str_pad($this->value, $len, chr(0), STR_PAD_LEFT);
  87  
  88                  $this->value = '0';
  89                  for ($i = 0; $i < $len; $i += 4) {
  90                      $this->value = bcmul($this->value, '4294967296', 0); // 4294967296 == 2**32
  91                      $this->value = bcadd(
  92                          $this->value,
  93                          0x1000000 * ord($x[$i]) + ((ord($x[$i + 1]) << 16) | (ord(
  94                              $x[$i + 2]
  95                          ) << 8) | ord($x[$i + 3])),
  96                          0
  97                      );
  98                  }
  99  
 100                  if ($this->is_negative) {
 101                      $this->value = '-' . $this->value;
 102                  }
 103                  break;
 104              case 16:
 105                  $x = (strlen($this->value) & 1) ? '0' . $this->value : $this->value;
 106                  $temp = new self(Strings::hex2bin($x), 256);
 107                  $this->value = $this->is_negative ? '-' . $temp->value : $temp->value;
 108                  $this->is_negative = false;
 109                  break;
 110              case 10:
 111                  // explicitly casting $x to a string is necessary, here, since doing $x[0] on -1 yields different
 112                  // results then doing it on '-1' does (modInverse does $x[0])
 113                  $this->value = $this->value === '-' ? '0' : (string)$this->value;
 114          }
 115      }
 116  
 117      /**
 118       * Converts a BigInteger to a base-10 number.
 119       *
 120       * @return string
 121       */
 122      public function toString()
 123      {
 124          if ($this->value === '0') {
 125              return '0';
 126          }
 127  
 128          return ltrim($this->value, '0');
 129      }
 130  
 131      /**
 132       * Converts a BigInteger to a byte string (eg. base-256).
 133       *
 134       * @param bool $twos_compliment
 135       * @return string
 136       */
 137      public function toBytes($twos_compliment = false)
 138      {
 139          if ($twos_compliment) {
 140              return $this->toBytesHelper();
 141          }
 142  
 143          $value = '';
 144          $current = $this->value;
 145  
 146          if ($current[0] == '-') {
 147              $current = substr($current, 1);
 148          }
 149  
 150          while (bccomp($current, '0', 0) > 0) {
 151              $temp = bcmod($current, '16777216');
 152              $value = chr($temp >> 16) . chr($temp >> 8) . chr($temp) . $value;
 153              $current = bcdiv($current, '16777216', 0);
 154          }
 155  
 156          return $this->precision > 0 ?
 157              substr(str_pad($value, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) :
 158              ltrim($value, chr(0));
 159      }
 160  
 161      /**
 162       * Adds two BigIntegers.
 163       *
 164       * @param BCMath $y
 165       * @return BCMath
 166       */
 167      public function add(BCMath $y)
 168      {
 169          $temp = new self();
 170          $temp->value = bcadd($this->value, $y->value);
 171  
 172          return $this->normalize($temp);
 173      }
 174  
 175      /**
 176       * Subtracts two BigIntegers.
 177       *
 178       * @param BCMath $y
 179       * @return BCMath
 180       */
 181      public function subtract(BCMath $y)
 182      {
 183          $temp = new self();
 184          $temp->value = bcsub($this->value, $y->value);
 185  
 186          return $this->normalize($temp);
 187      }
 188  
 189      /**
 190       * Multiplies two BigIntegers.
 191       *
 192       * @param BCMath $x
 193       * @return BCMath
 194       */
 195      public function multiply(BCMath $x)
 196      {
 197          $temp = new self();
 198          $temp->value = bcmul($this->value, $x->value);
 199  
 200          return $this->normalize($temp);
 201      }
 202  
 203      /**
 204       * Divides two BigIntegers.
 205       *
 206       * Returns an array whose first element contains the quotient and whose second element contains the
 207       * "common residue".  If the remainder would be positive, the "common residue" and the remainder are the
 208       * same.  If the remainder would be negative, the "common residue" is equal to the sum of the remainder
 209       * and the divisor (basically, the "common residue" is the first positive modulo).
 210       *
 211       * @param BCMath $y
 212       * @return array{static, static}
 213       */
 214      public function divide(BCMath $y)
 215      {
 216          $quotient = new self();
 217          $remainder = new self();
 218  
 219          $quotient->value = bcdiv($this->value, $y->value, 0);
 220          $remainder->value = bcmod($this->value, $y->value);
 221  
 222          if ($remainder->value[0] == '-') {
 223              $remainder->value = bcadd($remainder->value, $y->value[0] == '-' ? substr($y->value, 1) : $y->value, 0);
 224          }
 225  
 226          return [$this->normalize($quotient), $this->normalize($remainder)];
 227      }
 228  
 229      /**
 230       * Calculates modular inverses.
 231       *
 232       * Say you have (30 mod 17 * x mod 17) mod 17 == 1.  x can be found using modular inverses.
 233       *
 234       * @param BCMath $n
 235       * @return false|BCMath
 236       */
 237      public function modInverse(BCMath $n)
 238      {
 239          return $this->modInverseHelper($n);
 240      }
 241  
 242      /**
 243       * Calculates the greatest common divisor and Bezout's identity.
 244       *
 245       * Say you have 693 and 609.  The GCD is 21.  Bezout's identity states that there exist integers x and y such that
 246       * 693*x + 609*y == 21.  In point of fact, there are actually an infinite number of x and y combinations and which
 247       * combination is returned is dependent upon which mode is in use.  See
 248       * {@link http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity Bezout's identity - Wikipedia} for more information.
 249       *
 250       * @param BCMath $n
 251       * @return array{gcd: static, x: static, y: static}
 252       */
 253      public function extendedGCD(BCMath $n)
 254      {
 255          // it might be faster to use the binary xGCD algorithim here, as well, but (1) that algorithim works
 256          // best when the base is a power of 2 and (2) i don't think it'd make much difference, anyway.  as is,
 257          // the basic extended euclidean algorithim is what we're using.
 258  
 259          $u = $this->value;
 260          $v = $n->value;
 261  
 262          $a = '1';
 263          $b = '0';
 264          $c = '0';
 265          $d = '1';
 266  
 267          while (bccomp($v, '0', 0) != 0) {
 268              $q = bcdiv($u, $v, 0);
 269  
 270              $temp = $u;
 271              $u = $v;
 272              $v = bcsub($temp, bcmul($v, $q, 0), 0);
 273  
 274              $temp = $a;
 275              $a = $c;
 276              $c = bcsub($temp, bcmul($a, $q, 0), 0);
 277  
 278              $temp = $b;
 279              $b = $d;
 280              $d = bcsub($temp, bcmul($b, $q, 0), 0);
 281          }
 282  
 283          return [
 284              'gcd' => $this->normalize(new static($u)),
 285              'x' => $this->normalize(new static($a)),
 286              'y' => $this->normalize(new static($b))
 287          ];
 288      }
 289  
 290      /**
 291       * Calculates the greatest common divisor
 292       *
 293       * Say you have 693 and 609.  The GCD is 21.
 294       *
 295       * @param BCMath $n
 296       * @return BCMath
 297       */
 298      public function gcd(BCMath $n)
 299      {
 300          extract($this->extendedGCD($n));
 301          /** @var BCMath $gcd */
 302          return $gcd;
 303      }
 304  
 305      /**
 306       * Absolute value.
 307       *
 308       * @return BCMath
 309       */
 310      public function abs()
 311      {
 312          $temp = new static();
 313          $temp->value = strlen($this->value) && $this->value[0] == '-' ?
 314              substr($this->value, 1) :
 315              $this->value;
 316  
 317          return $temp;
 318      }
 319  
 320      /**
 321       * Logical And
 322       *
 323       * @param BCMath $x
 324       * @return BCMath
 325       */
 326      public function bitwise_and(BCMath $x)
 327      {
 328          return $this->bitwiseAndHelper($x);
 329      }
 330  
 331      /**
 332       * Logical Or
 333       *
 334       * @param BCMath $x
 335       * @return BCMath
 336       */
 337      public function bitwise_or(BCMath $x)
 338      {
 339          return $this->bitwiseXorHelper($x);
 340      }
 341  
 342      /**
 343       * Logical Exclusive Or
 344       *
 345       * @param BCMath $x
 346       * @return BCMath
 347       */
 348      public function bitwise_xor(BCMath $x)
 349      {
 350          return $this->bitwiseXorHelper($x);
 351      }
 352  
 353      /**
 354       * Logical Right Shift
 355       *
 356       * Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift.
 357       *
 358       * @param int $shift
 359       * @return BCMath
 360       */
 361      public function bitwise_rightShift($shift)
 362      {
 363          $temp = new static();
 364          $temp->value = bcdiv($this->value, bcpow('2', $shift, 0), 0);
 365  
 366          return $this->normalize($temp);
 367      }
 368  
 369      /**
 370       * Logical Left Shift
 371       *
 372       * Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift.
 373       *
 374       * @param int $shift
 375       * @return BCMath
 376       */
 377      public function bitwise_leftShift($shift)
 378      {
 379          $temp = new static();
 380          $temp->value = bcmul($this->value, bcpow('2', $shift, 0), 0);
 381  
 382          return $this->normalize($temp);
 383      }
 384  
 385      /**
 386       * Compares two numbers.
 387       *
 388       * Although one might think !$x->compare($y) means $x != $y, it, in fact, means the opposite.  The reason for this
 389       * is demonstrated thusly:
 390       *
 391       * $x  > $y: $x->compare($y)  > 0
 392       * $x  < $y: $x->compare($y)  < 0
 393       * $x == $y: $x->compare($y) == 0
 394       *
 395       * Note how the same comparison operator is used.  If you want to test for equality, use $x->equals($y).
 396       *
 397       * {@internal Could return $this->subtract($x), but that's not as fast as what we do do.}
 398       *
 399       * @param BCMath $y
 400       * @return int in case < 0 if $this is less than $y; > 0 if $this is greater than $y, and 0 if they are equal.
 401       * @see self::equals()
 402       */
 403      public function compare(BCMath $y)
 404      {
 405          return bccomp($this->value, $y->value, 0);
 406      }
 407  
 408      /**
 409       * Tests the equality of two numbers.
 410       *
 411       * If you need to see if one number is greater than or less than another number, use BigInteger::compare()
 412       *
 413       * @param BCMath $x
 414       * @return bool
 415       */
 416      public function equals(BCMath $x)
 417      {
 418          return $this->value == $x->value;
 419      }
 420  
 421      /**
 422       * Performs modular exponentiation.
 423       *
 424       * @param BCMath $e
 425       * @param BCMath $n
 426       * @return BCMath
 427       */
 428      public function modPow(BCMath $e, BCMath $n)
 429      {
 430          return $this->powModOuter($e, $n);
 431      }
 432  
 433      /**
 434       * Performs modular exponentiation.
 435       *
 436       * Alias for modPow().
 437       *
 438       * @param BCMath $e
 439       * @param BCMath $n
 440       * @return BCMath
 441       */
 442      public function powMod(BCMath $e, BCMath $n)
 443      {
 444          return $this->powModOuter($e, $n);
 445      }
 446  
 447      /**
 448       * Performs modular exponentiation.
 449       *
 450       * @param BCMath $e
 451       * @param BCMath $n
 452       * @return BCMath
 453       */
 454      protected function powModInner(BCMath $e, BCMath $n)
 455      {
 456          try {
 457              $class = static::$modexpEngine[static::class];
 458              return $class::powModHelper($this, $e, $n, static::class);
 459          } catch (\Exception $err) {
 460              return BCMath\DefaultEngine::powModHelper($this, $e, $n, static::class);
 461          }
 462      }
 463  
 464      /**
 465       * Normalize
 466       *
 467       * Removes leading zeros and truncates (if necessary) to maintain the appropriate precision
 468       *
 469       * @param BCMath $result
 470       * @return BCMath
 471       */
 472      protected function normalize(BCMath $result)
 473      {
 474          $result->precision = $this->precision;
 475          $result->bitmask = $this->bitmask;
 476  
 477          if ($result->bitmask !== false) {
 478              $result->value = bcmod($result->value, $result->bitmask->value);
 479          }
 480  
 481          return $result;
 482      }
 483  
 484      /**
 485       * Generate a random prime number between a range
 486       *
 487       * If there's not a prime within the given range, false will be returned.
 488       *
 489       * @param BCMath $min
 490       * @param BCMath $max
 491       * @return false|BCMath
 492       */
 493      public static function randomRangePrime(BCMath $min, BCMath $max)
 494      {
 495          return self::randomRangePrimeOuter($min, $max);
 496      }
 497  
 498      /**
 499       * Generate a random number between a range
 500       *
 501       * Returns a random number between $min and $max where $min and $max
 502       * can be defined using one of the two methods:
 503       *
 504       * BigInteger::randomRange($min, $max)
 505       * BigInteger::randomRange($max, $min)
 506       *
 507       * @param BCMath $min
 508       * @param BCMath $max
 509       * @return BCMath
 510       */
 511      public static function randomRange(BCMath $min, BCMath $max)
 512      {
 513          return self::randomRangeHelper($min, $max);
 514      }
 515  
 516      /**
 517       * Make the current number odd
 518       *
 519       * If the current number is odd it'll be unchanged.  If it's even, one will be added to it.
 520       *
 521       * @see self::randomPrime()
 522       */
 523      protected function make_odd()
 524      {
 525          if (!$this->isOdd()) {
 526              $this->value = bcadd($this->value, '1');
 527          }
 528      }
 529  
 530      /**
 531       * Test the number against small primes.
 532       *
 533       * @see self::isPrime()
 534       */
 535      protected function testSmallPrimes()
 536      {
 537          if ($this->value === '1') {
 538              return false;
 539          }
 540          if ($this->value === '2') {
 541              return true;
 542          }
 543          if ($this->value[strlen($this->value) - 1] % 2 == 0) {
 544              return false;
 545          }
 546  
 547          $value = $this->value;
 548  
 549          foreach (self::PRIMES as $prime) {
 550              $r = bcmod($this->value, $prime);
 551              if ($r == '0') {
 552                  return $this->value == $prime;
 553              }
 554          }
 555  
 556          return true;
 557      }
 558  
 559      /**
 560       * Scan for 1 and right shift by that amount
 561       *
 562       * ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s));
 563       *
 564       * @param BCMath $r
 565       * @return int
 566       * @see self::isPrime()
 567       */
 568      public static function scan1divide(BCMath $r)
 569      {
 570          $r_value = &$r->value;
 571          $s = 0;
 572          // if $n was 1, $r would be 0 and this would be an infinite loop, hence our $this->equals(static::$one[static::class]) check earlier
 573          while ($r_value[strlen($r_value) - 1] % 2 == 0) {
 574              $r_value = bcdiv($r_value, '2', 0);
 575              ++$s;
 576          }
 577  
 578          return $s;
 579      }
 580  
 581      /**
 582       * Performs exponentiation.
 583       *
 584       * @param BCMath $n
 585       * @return BCMath
 586       */
 587      public function pow(BCMath $n)
 588      {
 589          $temp = new self();
 590          $temp->value = bcpow($this->value, $n->value);
 591  
 592          return $this->normalize($temp);
 593      }
 594  
 595      /**
 596       * Return the minimum BigInteger between an arbitrary number of BigIntegers.
 597       *
 598       * @param BCMath ...$nums
 599       * @return BCMath
 600       */
 601      public static function min(BCMath ...$nums)
 602      {
 603          return self::minHelper($nums);
 604      }
 605  
 606      /**
 607       * Return the maximum BigInteger between an arbitrary number of BigIntegers.
 608       *
 609       * @param BCMath ...$nums
 610       * @return BCMath
 611       */
 612      public static function max(BCMath ...$nums)
 613      {
 614          return self::maxHelper($nums);
 615      }
 616  
 617      /**
 618       * Tests BigInteger to see if it is between two integers, inclusive
 619       *
 620       * @param BCMath $min
 621       * @param BCMath $max
 622       * @return bool
 623       */
 624      public function between(BCMath $min, BCMath $max)
 625      {
 626          return $this->compare($min) >= 0 && $this->compare($max) <= 0;
 627      }
 628  
 629      /**
 630       * Set Bitmask
 631       *
 632       * @param int $bits
 633       * @return Engine
 634       * @see self::setPrecision()
 635       */
 636      protected static function setBitmask($bits)
 637      {
 638          $temp = parent::setBitmask($bits);
 639          return $temp->add(static::$one[static::class]);
 640      }
 641  
 642      /**
 643       * Is Odd?
 644       *
 645       * @return bool
 646       */
 647      public function isOdd()
 648      {
 649          return $this->value[strlen($this->value) - 1] % 2 == 1;
 650      }
 651  
 652      /**
 653       * Tests if a bit is set
 654       *
 655       * @return bool
 656       */
 657      public function testBit($x)
 658      {
 659          return bccomp(
 660              bcmod($this->value, bcpow('2', $x + 1, 0)),
 661              bcpow('2', $x, 0),
 662              0
 663          ) >= 0;
 664      }
 665  
 666      /**
 667       * Is Negative?
 668       *
 669       * @return bool
 670       */
 671      public function isNegative()
 672      {
 673          return strlen($this->value) && $this->value[0] == '-';
 674      }
 675  
 676      /**
 677       * Negate
 678       *
 679       * Given $k, returns -$k
 680       *
 681       * @return BCMath
 682       */
 683      public function negate()
 684      {
 685          $temp = clone $this;
 686  
 687          if (!strlen($temp->value)) {
 688              return $temp;
 689          }
 690  
 691          $temp->value = $temp->value[0] == '-' ?
 692              substr($this->value, 1) :
 693              '-' . $this->value;
 694  
 695          return $temp;
 696      }
 697  }