[Summary view] [Print] [Text view]

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