[Summary view] [Print] [Text view]

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