[ Index ]

PHP Cross Reference of DokuWiki

title

Body

[close]

/vendor/phpseclib/phpseclib/phpseclib/Math/ -> BigInteger.php (source)

   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
  10   *
  11   * {@internal (all DocBlock comments regarding implementation - such as the one that follows - refer to the
  12   * {@link self::MODE_INTERNAL self::MODE_INTERNAL} mode)
  13   *
  14   * BigInteger uses base-2**26 to perform operations such as multiplication and division and
  15   * base-2**52 (ie. two base 2**26 digits) to perform addition and subtraction.  Because the largest possible
  16   * value when multiplying two base-2**26 numbers together is a base-2**52 number, double precision floating
  17   * point numbers - numbers that should be supported on most hardware and whose significand is 53 bits - are
  18   * used.  As a consequence, bitwise operators such as >> and << cannot be used, nor can the modulo operator %,
  19   * which only supports integers.  Although this fact will slow this library down, the fact that such a high
  20   * base is being used should more than compensate.
  21   *
  22   * Numbers are stored in {@link http://en.wikipedia.org/wiki/Endianness little endian} format.  ie.
  23   * (new \phpseclib\Math\BigInteger(pow(2, 26)))->value = array(0, 1)
  24   *
  25   * Useful resources are as follows:
  26   *
  27   *  - {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf Handbook of Applied Cryptography (HAC)}
  28   *  - {@link http://math.libtomcrypt.com/files/tommath.pdf Multi-Precision Math (MPM)}
  29   *  - Java's BigInteger classes.  See /j2se/src/share/classes/java/math in jdk-1_5_0-src-jrl.zip
  30   *
  31   * Here's an example of how to use this library:
  32   * <code>
  33   * <?php
  34   *    $a = new \phpseclib\Math\BigInteger(2);
  35   *    $b = new \phpseclib\Math\BigInteger(3);
  36   *
  37   *    $c = $a->add($b);
  38   *
  39   *    echo $c->toString(); // outputs 5
  40   * ?>
  41   * </code>
  42   *
  43   * @category  Math
  44   * @package   BigInteger
  45   * @author    Jim Wigginton <terrafrost@php.net>
  46   * @copyright 2006 Jim Wigginton
  47   * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
  48   */
  49  
  50  namespace phpseclib\Math;
  51  
  52  use phpseclib\Crypt\Random;
  53  
  54  /**
  55   * Pure-PHP arbitrary precision integer arithmetic library. Supports base-2, base-10, base-16, and base-256
  56   * numbers.
  57   *
  58   * @package BigInteger
  59   * @author  Jim Wigginton <terrafrost@php.net>
  60   * @access  public
  61   */
  62  class BigInteger
  63  {
  64      /**#@+
  65       * Reduction constants
  66       *
  67       * @access private
  68       * @see BigInteger::_reduce()
  69       */
  70      /**
  71       * @see BigInteger::_montgomery()
  72       * @see BigInteger::_prepMontgomery()
  73       */
  74      const MONTGOMERY = 0;
  75      /**
  76       * @see BigInteger::_barrett()
  77       */
  78      const BARRETT = 1;
  79      /**
  80       * @see BigInteger::_mod2()
  81       */
  82      const POWEROF2 = 2;
  83      /**
  84       * @see BigInteger::_remainder()
  85       */
  86      const CLASSIC = 3;
  87      /**
  88       * @see BigInteger::__clone()
  89       */
  90      const NONE = 4;
  91      /**#@-*/
  92  
  93      /**#@+
  94       * Array constants
  95       *
  96       * Rather than create a thousands and thousands of new BigInteger objects in repeated function calls to add() and
  97       * multiply() or whatever, we'll just work directly on arrays, taking them in as parameters and returning them.
  98       *
  99       * @access private
 100      */
 101      /**
 102       * $result[self::VALUE] contains the value.
 103       */
 104      const VALUE = 0;
 105      /**
 106       * $result[self::SIGN] contains the sign.
 107       */
 108      const SIGN = 1;
 109      /**#@-*/
 110  
 111      /**#@+
 112       * @access private
 113       * @see BigInteger::_montgomery()
 114       * @see BigInteger::_barrett()
 115      */
 116      /**
 117       * Cache constants
 118       *
 119       * $cache[self::VARIABLE] tells us whether or not the cached data is still valid.
 120       */
 121      const VARIABLE = 0;
 122      /**
 123       * $cache[self::DATA] contains the cached data.
 124       */
 125      const DATA = 1;
 126      /**#@-*/
 127  
 128      /**#@+
 129       * Mode constants.
 130       *
 131       * @access private
 132       * @see BigInteger::__construct()
 133      */
 134      /**
 135       * To use the pure-PHP implementation
 136       */
 137      const MODE_INTERNAL = 1;
 138      /**
 139       * To use the BCMath library
 140       *
 141       * (if enabled; otherwise, the internal implementation will be used)
 142       */
 143      const MODE_BCMATH = 2;
 144      /**
 145       * To use the GMP library
 146       *
 147       * (if present; otherwise, either the BCMath or the internal implementation will be used)
 148       */
 149      const MODE_GMP = 3;
 150      /**#@-*/
 151  
 152      /**
 153       * Karatsuba Cutoff
 154       *
 155       * At what point do we switch between Karatsuba multiplication and schoolbook long multiplication?
 156       *
 157       * @access private
 158       */
 159      const KARATSUBA_CUTOFF = 25;
 160  
 161      /**#@+
 162       * Static properties used by the pure-PHP implementation.
 163       *
 164       * @see __construct()
 165       */
 166      protected static $base;
 167      protected static $baseFull;
 168      protected static $maxDigit;
 169      protected static $msb;
 170  
 171      /**
 172       * $max10 in greatest $max10Len satisfying
 173       * $max10 = 10**$max10Len <= 2**$base.
 174       */
 175      protected static $max10;
 176  
 177      /**
 178       * $max10Len in greatest $max10Len satisfying
 179       * $max10 = 10**$max10Len <= 2**$base.
 180       */
 181      protected static $max10Len;
 182      protected static $maxDigit2;
 183      /**#@-*/
 184  
 185      /**
 186       * Holds the BigInteger's value.
 187       *
 188       * @var array
 189       * @access private
 190       */
 191      var $value;
 192  
 193      /**
 194       * Holds the BigInteger's magnitude.
 195       *
 196       * @var bool
 197       * @access private
 198       */
 199      var $is_negative = false;
 200  
 201      /**
 202       * Precision
 203       *
 204       * @see self::setPrecision()
 205       * @access private
 206       */
 207      var $precision = -1;
 208  
 209      /**
 210       * Precision Bitmask
 211       *
 212       * @see self::setPrecision()
 213       * @access private
 214       */
 215      var $bitmask = false;
 216  
 217      /**
 218       * Mode independent value used for serialization.
 219       *
 220       * If the bcmath or gmp extensions are installed $this->value will be a non-serializable resource, hence the need for
 221       * a variable that'll be serializable regardless of whether or not extensions are being used.  Unlike $this->value,
 222       * however, $this->hex is only calculated when $this->__sleep() is called.
 223       *
 224       * @see self::__sleep()
 225       * @see self::__wakeup()
 226       * @var string
 227       * @access private
 228       */
 229      var $hex;
 230  
 231      /**
 232       * Converts base-2, base-10, base-16, and binary strings (base-256) to BigIntegers.
 233       *
 234       * If the second parameter - $base - is negative, then it will be assumed that the number's are encoded using
 235       * two's compliment.  The sole exception to this is -10, which is treated the same as 10 is.
 236       *
 237       * Here's an example:
 238       * <code>
 239       * <?php
 240       *    $a = new \phpseclib\Math\BigInteger('0x32', 16); // 50 in base-16
 241       *
 242       *    echo $a->toString(); // outputs 50
 243       * ?>
 244       * </code>
 245       *
 246       * @param int|string|resource $x base-10 number or base-$base number if $base set.
 247       * @param int $base
 248       * @return \phpseclib\Math\BigInteger
 249       * @access public
 250       */
 251      function __construct($x = 0, $base = 10)
 252      {
 253          if (!defined('MATH_BIGINTEGER_MODE')) {
 254              switch (true) {
 255                  case extension_loaded('gmp'):
 256                      define('MATH_BIGINTEGER_MODE', self::MODE_GMP);
 257                      break;
 258                  case extension_loaded('bcmath'):
 259                      define('MATH_BIGINTEGER_MODE', self::MODE_BCMATH);
 260                      break;
 261                  default:
 262                      define('MATH_BIGINTEGER_MODE', self::MODE_INTERNAL);
 263              }
 264          }
 265  
 266          if (extension_loaded('openssl') && !defined('MATH_BIGINTEGER_OPENSSL_DISABLE') && !defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
 267              // some versions of XAMPP have mismatched versions of OpenSSL which causes it not to work
 268              $versions = array();
 269  
 270              // avoid generating errors (even with suppression) when phpinfo() is disabled (common in production systems)
 271              if (function_exists('phpinfo')) {
 272                  ob_start();
 273                  @phpinfo();
 274                  $content = ob_get_contents();
 275                  ob_end_clean();
 276  
 277                  preg_match_all('#OpenSSL (Header|Library) Version(.*)#im', $content, $matches);
 278  
 279                  if (!empty($matches[1])) {
 280                      for ($i = 0; $i < count($matches[1]); $i++) {
 281                          $fullVersion = trim(str_replace('=>', '', strip_tags($matches[2][$i])));
 282  
 283                          // Remove letter part in OpenSSL version
 284                          if (!preg_match('/(\d+\.\d+\.\d+)/i', $fullVersion, $m)) {
 285                              $versions[$matches[1][$i]] = $fullVersion;
 286                          } else {
 287                              $versions[$matches[1][$i]] = $m[0];
 288                          }
 289                      }
 290                  }
 291              }
 292  
 293              // it doesn't appear that OpenSSL versions were reported upon until PHP 5.3+
 294              switch (true) {
 295                  case !isset($versions['Header']):
 296                  case !isset($versions['Library']):
 297                  case $versions['Header'] == $versions['Library']:
 298                  case version_compare($versions['Header'], '1.0.0') >= 0 && version_compare($versions['Library'], '1.0.0') >= 0:
 299                      define('MATH_BIGINTEGER_OPENSSL_ENABLED', true);
 300                      break;
 301                  default:
 302                      define('MATH_BIGINTEGER_OPENSSL_DISABLE', true);
 303              }
 304          }
 305  
 306          if (!defined('PHP_INT_SIZE')) {
 307              define('PHP_INT_SIZE', 4);
 308          }
 309  
 310          if (empty(self::$base) && MATH_BIGINTEGER_MODE == self::MODE_INTERNAL) {
 311              switch (PHP_INT_SIZE) {
 312                  case 8: // use 64-bit integers if int size is 8 bytes
 313                      self::$base      = 31;
 314                      self::$baseFull  = 0x80000000;
 315                      self::$maxDigit  = 0x7FFFFFFF;
 316                      self::$msb       = 0x40000000;
 317                      self::$max10     = 1000000000;
 318                      self::$max10Len  = 9;
 319                      self::$maxDigit2 = pow(2, 62);
 320                      break;
 321                  //case 4: // use 64-bit floats if int size is 4 bytes
 322                  default:
 323                      self::$base      = 26;
 324                      self::$baseFull  = 0x4000000;
 325                      self::$maxDigit  = 0x3FFFFFF;
 326                      self::$msb       = 0x2000000;
 327                      self::$max10     = 10000000;
 328                      self::$max10Len  = 7;
 329                      self::$maxDigit2 = pow(2, 52); // pow() prevents truncation
 330              }
 331          }
 332  
 333          switch (MATH_BIGINTEGER_MODE) {
 334              case self::MODE_GMP:
 335                  switch (true) {
 336                      case is_resource($x) && get_resource_type($x) == 'GMP integer':
 337                      // PHP 5.6 switched GMP from using resources to objects
 338                      case $x instanceof \GMP:
 339                          $this->value = $x;
 340                          return;
 341                  }
 342                  $this->value = gmp_init(0);
 343                  break;
 344              case self::MODE_BCMATH:
 345                  $this->value = '0';
 346                  break;
 347              default:
 348                  $this->value = array();
 349          }
 350  
 351          // '0' counts as empty() but when the base is 256 '0' is equal to ord('0') or 48
 352          // '0' is the only value like this per http://php.net/empty
 353          if (empty($x) && (abs($base) != 256 || $x !== '0')) {
 354              return;
 355          }
 356  
 357          switch ($base) {
 358              case -256:
 359                  if (ord($x[0]) & 0x80) {
 360                      $x = ~$x;
 361                      $this->is_negative = true;
 362                  }
 363              case 256:
 364                  switch (MATH_BIGINTEGER_MODE) {
 365                      case self::MODE_GMP:
 366                          $this->value = function_exists('gmp_import') ?
 367                              gmp_import($x) :
 368                              gmp_init('0x' . bin2hex($x));
 369                          if ($this->is_negative) {
 370                              $this->value = gmp_neg($this->value);
 371                          }
 372                          break;
 373                      case self::MODE_BCMATH:
 374                          // round $len to the nearest 4 (thanks, DavidMJ!)
 375                          $len = (strlen($x) + 3) & ~3;
 376  
 377                          $x = str_pad($x, $len, chr(0), STR_PAD_LEFT);
 378  
 379                          for ($i = 0; $i < $len; $i+= 4) {
 380                              $this->value = bcmul($this->value, '4294967296', 0); // 4294967296 == 2**32
 381                              $this->value = bcadd($this->value, 0x1000000 * ord($x[$i]) + ((ord($x[$i + 1]) << 16) | (ord($x[$i + 2]) << 8) | ord($x[$i + 3])), 0);
 382                          }
 383  
 384                          if ($this->is_negative) {
 385                              $this->value = '-' . $this->value;
 386                          }
 387  
 388                          break;
 389                      // converts a base-2**8 (big endian / msb) number to base-2**26 (little endian / lsb)
 390                      default:
 391                          while (strlen($x)) {
 392                              $this->value[] = $this->_bytes2int($this->_base256_rshift($x, self::$base));
 393                          }
 394                  }
 395  
 396                  if ($this->is_negative) {
 397                      if (MATH_BIGINTEGER_MODE != self::MODE_INTERNAL) {
 398                          $this->is_negative = false;
 399                      }
 400                      $temp = $this->add(new static('-1'));
 401                      $this->value = $temp->value;
 402                  }
 403                  break;
 404              case 16:
 405              case -16:
 406                  if ($base > 0 && $x[0] == '-') {
 407                      $this->is_negative = true;
 408                      $x = substr($x, 1);
 409                  }
 410  
 411                  $x = preg_replace('#^(?:0x)?([A-Fa-f0-9]*).*#s', '$1', $x);
 412  
 413                  $is_negative = false;
 414                  if ($base < 0 && hexdec($x[0]) >= 8) {
 415                      $this->is_negative = $is_negative = true;
 416                      $x = bin2hex(~pack('H*', $x));
 417                  }
 418  
 419                  switch (MATH_BIGINTEGER_MODE) {
 420                      case self::MODE_GMP:
 421                          $temp = $this->is_negative ? '-0x' . $x : '0x' . $x;
 422                          $this->value = gmp_init($temp);
 423                          $this->is_negative = false;
 424                          break;
 425                      case self::MODE_BCMATH:
 426                          $x = (strlen($x) & 1) ? '0' . $x : $x;
 427                          $temp = new static(pack('H*', $x), 256);
 428                          $this->value = $this->is_negative ? '-' . $temp->value : $temp->value;
 429                          $this->is_negative = false;
 430                          break;
 431                      default:
 432                          $x = (strlen($x) & 1) ? '0' . $x : $x;
 433                          $temp = new static(pack('H*', $x), 256);
 434                          $this->value = $temp->value;
 435                  }
 436  
 437                  if ($is_negative) {
 438                      $temp = $this->add(new static('-1'));
 439                      $this->value = $temp->value;
 440                  }
 441                  break;
 442              case 10:
 443              case -10:
 444                  // (?<!^)(?:-).*: find any -'s that aren't at the beginning and then any characters that follow that
 445                  // (?<=^|-)0*: find any 0's that are preceded by the start of the string or by a - (ie. octals)
 446                  // [^-0-9].*: find any non-numeric characters and then any characters that follow that
 447                  $x = preg_replace('#(?<!^)(?:-).*|(?<=^|-)0*|[^-0-9].*#s', '', $x);
 448                  if (!strlen($x) || $x == '-') {
 449                      $x = '0';
 450                  }
 451  
 452                  switch (MATH_BIGINTEGER_MODE) {
 453                      case self::MODE_GMP:
 454                          $this->value = gmp_init($x);
 455                          break;
 456                      case self::MODE_BCMATH:
 457                          // explicitly casting $x to a string is necessary, here, since doing $x[0] on -1 yields different
 458                          // results then doing it on '-1' does (modInverse does $x[0])
 459                          $this->value = $x === '-' ? '0' : (string) $x;
 460                          break;
 461                      default:
 462                          $temp = new static();
 463  
 464                          $multiplier = new static();
 465                          $multiplier->value = array(self::$max10);
 466  
 467                          if ($x[0] == '-') {
 468                              $this->is_negative = true;
 469                              $x = substr($x, 1);
 470                          }
 471  
 472                          $x = str_pad($x, strlen($x) + ((self::$max10Len - 1) * strlen($x)) % self::$max10Len, 0, STR_PAD_LEFT);
 473                          while (strlen($x)) {
 474                              $temp = $temp->multiply($multiplier);
 475                              $temp = $temp->add(new static($this->_int2bytes(substr($x, 0, self::$max10Len)), 256));
 476                              $x = substr($x, self::$max10Len);
 477                          }
 478  
 479                          $this->value = $temp->value;
 480                  }
 481                  break;
 482              case 2: // base-2 support originally implemented by Lluis Pamies - thanks!
 483              case -2:
 484                  if ($base > 0 && $x[0] == '-') {
 485                      $this->is_negative = true;
 486                      $x = substr($x, 1);
 487                  }
 488  
 489                  $x = preg_replace('#^([01]*).*#s', '$1', $x);
 490                  $x = str_pad($x, strlen($x) + (3 * strlen($x)) % 4, 0, STR_PAD_LEFT);
 491  
 492                  $str = '0x';
 493                  while (strlen($x)) {
 494                      $part = substr($x, 0, 4);
 495                      $str.= dechex(bindec($part));
 496                      $x = substr($x, 4);
 497                  }
 498  
 499                  if ($this->is_negative) {
 500                      $str = '-' . $str;
 501                  }
 502  
 503                  $temp = new static($str, 8 * $base); // ie. either -16 or +16
 504                  $this->value = $temp->value;
 505                  $this->is_negative = $temp->is_negative;
 506  
 507                  break;
 508              default:
 509                  // base not supported, so we'll let $this == 0
 510          }
 511      }
 512  
 513      /**
 514       * Converts a BigInteger to a byte string (eg. base-256).
 515       *
 516       * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
 517       * saved as two's compliment.
 518       *
 519       * Here's an example:
 520       * <code>
 521       * <?php
 522       *    $a = new \phpseclib\Math\BigInteger('65');
 523       *
 524       *    echo $a->toBytes(); // outputs chr(65)
 525       * ?>
 526       * </code>
 527       *
 528       * @param bool $twos_compliment
 529       * @return string
 530       * @access public
 531       * @internal Converts a base-2**26 number to base-2**8
 532       */
 533      function toBytes($twos_compliment = false)
 534      {
 535          if ($twos_compliment) {
 536              $comparison = $this->compare(new static());
 537              if ($comparison == 0) {
 538                  return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
 539              }
 540  
 541              $temp = $comparison < 0 ? $this->add(new static(1)) : $this->copy();
 542              $bytes = $temp->toBytes();
 543  
 544              if (!strlen($bytes)) { // eg. if the number we're trying to convert is -1
 545                  $bytes = chr(0);
 546              }
 547  
 548              if ($this->precision <= 0 && (ord($bytes[0]) & 0x80)) {
 549                  $bytes = chr(0) . $bytes;
 550              }
 551  
 552              return $comparison < 0 ? ~$bytes : $bytes;
 553          }
 554  
 555          switch (MATH_BIGINTEGER_MODE) {
 556              case self::MODE_GMP:
 557                  if (gmp_cmp($this->value, gmp_init(0)) == 0) {
 558                      return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
 559                  }
 560  
 561                  if (function_exists('gmp_export')) {
 562                      $temp = gmp_export($this->value);
 563                  } else {
 564                      $temp = gmp_strval(gmp_abs($this->value), 16);
 565                      $temp = (strlen($temp) & 1) ? '0' . $temp : $temp;
 566                      $temp = pack('H*', $temp);
 567                  }
 568  
 569                  return $this->precision > 0 ?
 570                      substr(str_pad($temp, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) :
 571                      ltrim($temp, chr(0));
 572              case self::MODE_BCMATH:
 573                  if ($this->value === '0') {
 574                      return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
 575                  }
 576  
 577                  $value = '';
 578                  $current = $this->value;
 579  
 580                  if ($current[0] == '-') {
 581                      $current = substr($current, 1);
 582                  }
 583  
 584                  while (bccomp($current, '0', 0) > 0) {
 585                      $temp = bcmod($current, '16777216');
 586                      $value = chr($temp >> 16) . chr($temp >> 8) . chr($temp) . $value;
 587                      $current = bcdiv($current, '16777216', 0);
 588                  }
 589  
 590                  return $this->precision > 0 ?
 591                      substr(str_pad($value, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) :
 592                      ltrim($value, chr(0));
 593          }
 594  
 595          if (!count($this->value)) {
 596              return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
 597          }
 598          $result = $this->_int2bytes($this->value[count($this->value) - 1]);
 599  
 600          $temp = $this->copy();
 601  
 602          for ($i = count($temp->value) - 2; $i >= 0; --$i) {
 603              $temp->_base256_lshift($result, self::$base);
 604              $result = $result | str_pad($temp->_int2bytes($temp->value[$i]), strlen($result), chr(0), STR_PAD_LEFT);
 605          }
 606  
 607          return $this->precision > 0 ?
 608              str_pad(substr($result, -(($this->precision + 7) >> 3)), ($this->precision + 7) >> 3, chr(0), STR_PAD_LEFT) :
 609              $result;
 610      }
 611  
 612      /**
 613       * Converts a BigInteger to a hex string (eg. base-16)).
 614       *
 615       * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
 616       * saved as two's compliment.
 617       *
 618       * Here's an example:
 619       * <code>
 620       * <?php
 621       *    $a = new \phpseclib\Math\BigInteger('65');
 622       *
 623       *    echo $a->toHex(); // outputs '41'
 624       * ?>
 625       * </code>
 626       *
 627       * @param bool $twos_compliment
 628       * @return string
 629       * @access public
 630       * @internal Converts a base-2**26 number to base-2**8
 631       */
 632      function toHex($twos_compliment = false)
 633      {
 634          return bin2hex($this->toBytes($twos_compliment));
 635      }
 636  
 637      /**
 638       * Converts a BigInteger to a bit string (eg. base-2).
 639       *
 640       * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
 641       * saved as two's compliment.
 642       *
 643       * Here's an example:
 644       * <code>
 645       * <?php
 646       *    $a = new \phpseclib\Math\BigInteger('65');
 647       *
 648       *    echo $a->toBits(); // outputs '1000001'
 649       * ?>
 650       * </code>
 651       *
 652       * @param bool $twos_compliment
 653       * @return string
 654       * @access public
 655       * @internal Converts a base-2**26 number to base-2**2
 656       */
 657      function toBits($twos_compliment = false)
 658      {
 659          $hex = $this->toHex($twos_compliment);
 660          $bits = '';
 661          for ($i = strlen($hex) - 6, $start = strlen($hex) % 6; $i >= $start; $i-=6) {
 662              $bits = str_pad(decbin(hexdec(substr($hex, $i, 6))), 24, '0', STR_PAD_LEFT) . $bits;
 663          }
 664          if ($start) { // hexdec('') == 0
 665              $bits = str_pad(decbin(hexdec(substr($hex, 0, $start))), 8 * $start, '0', STR_PAD_LEFT) . $bits;
 666          }
 667          $result = $this->precision > 0 ? substr($bits, -$this->precision) : ltrim($bits, '0');
 668  
 669          if ($twos_compliment && $this->compare(new static()) > 0 && $this->precision <= 0) {
 670              return '0' . $result;
 671          }
 672  
 673          return $result;
 674      }
 675  
 676      /**
 677       * Converts a BigInteger to a base-10 number.
 678       *
 679       * Here's an example:
 680       * <code>
 681       * <?php
 682       *    $a = new \phpseclib\Math\BigInteger('50');
 683       *
 684       *    echo $a->toString(); // outputs 50
 685       * ?>
 686       * </code>
 687       *
 688       * @return string
 689       * @access public
 690       * @internal Converts a base-2**26 number to base-10**7 (which is pretty much base-10)
 691       */
 692      function toString()
 693      {
 694          switch (MATH_BIGINTEGER_MODE) {
 695              case self::MODE_GMP:
 696                  return gmp_strval($this->value);
 697              case self::MODE_BCMATH:
 698                  if ($this->value === '0') {
 699                      return '0';
 700                  }
 701  
 702                  return ltrim($this->value, '0');
 703          }
 704  
 705          if (!count($this->value)) {
 706              return '0';
 707          }
 708  
 709          $temp = $this->copy();
 710          $temp->bitmask = false;
 711          $temp->is_negative = false;
 712  
 713          $divisor = new static();
 714          $divisor->value = array(self::$max10);
 715          $result = '';
 716          while (count($temp->value)) {
 717              list($temp, $mod) = $temp->divide($divisor);
 718              $result = str_pad(isset($mod->value[0]) ? $mod->value[0] : '', self::$max10Len, '0', STR_PAD_LEFT) . $result;
 719          }
 720          $result = ltrim($result, '0');
 721          if (empty($result)) {
 722              $result = '0';
 723          }
 724  
 725          if ($this->is_negative) {
 726              $result = '-' . $result;
 727          }
 728  
 729          return $result;
 730      }
 731  
 732      /**
 733       * Copy an object
 734       *
 735       * PHP5 passes objects by reference while PHP4 passes by value.  As such, we need a function to guarantee
 736       * that all objects are passed by value, when appropriate.  More information can be found here:
 737       *
 738       * {@link http://php.net/language.oop5.basic#51624}
 739       *
 740       * @access public
 741       * @see self::__clone()
 742       * @return \phpseclib\Math\BigInteger
 743       */
 744      function copy()
 745      {
 746          $temp = new static();
 747          $temp->value = $this->value;
 748          $temp->is_negative = $this->is_negative;
 749          $temp->precision = $this->precision;
 750          $temp->bitmask = $this->bitmask;
 751          return $temp;
 752      }
 753  
 754      /**
 755       *  __toString() magic method
 756       *
 757       * Will be called, automatically, if you're supporting just PHP5.  If you're supporting PHP4, you'll need to call
 758       * toString().
 759       *
 760       * @access public
 761       * @internal Implemented per a suggestion by Techie-Michael - thanks!
 762       */
 763      function __toString()
 764      {
 765          return $this->toString();
 766      }
 767  
 768      /**
 769       * __clone() magic method
 770       *
 771       * Although you can call BigInteger::__toString() directly in PHP5, you cannot call BigInteger::__clone() directly
 772       * in PHP5.  You can in PHP4 since it's not a magic method, but in PHP5, you have to call it by using the PHP5
 773       * only syntax of $y = clone $x.  As such, if you're trying to write an application that works on both PHP4 and
 774       * PHP5, call BigInteger::copy(), instead.
 775       *
 776       * @access public
 777       * @see self::copy()
 778       * @return \phpseclib\Math\BigInteger
 779       */
 780      function __clone()
 781      {
 782          return $this->copy();
 783      }
 784  
 785      /**
 786       *  __sleep() magic method
 787       *
 788       * Will be called, automatically, when serialize() is called on a BigInteger object.
 789       *
 790       * @see self::__wakeup()
 791       * @access public
 792       */
 793      function __sleep()
 794      {
 795          $this->hex = $this->toHex(true);
 796          $vars = array('hex');
 797          if ($this->precision > 0) {
 798              $vars[] = 'precision';
 799          }
 800          return $vars;
 801      }
 802  
 803      /**
 804       *  __wakeup() magic method
 805       *
 806       * Will be called, automatically, when unserialize() is called on a BigInteger object.
 807       *
 808       * @see self::__sleep()
 809       * @access public
 810       */
 811      function __wakeup()
 812      {
 813          $temp = new static($this->hex, -16);
 814          $this->value = $temp->value;
 815          $this->is_negative = $temp->is_negative;
 816          if ($this->precision > 0) {
 817              // recalculate $this->bitmask
 818              $this->setPrecision($this->precision);
 819          }
 820      }
 821  
 822      /**
 823       *  __debugInfo() magic method
 824       *
 825       * Will be called, automatically, when print_r() or var_dump() are called
 826       *
 827       * @access public
 828       */
 829      function __debugInfo()
 830      {
 831          $opts = array();
 832          switch (MATH_BIGINTEGER_MODE) {
 833              case self::MODE_GMP:
 834                  $engine = 'gmp';
 835                  break;
 836              case self::MODE_BCMATH:
 837                  $engine = 'bcmath';
 838                  break;
 839              case self::MODE_INTERNAL:
 840                  $engine = 'internal';
 841                  $opts[] = PHP_INT_SIZE == 8 ? '64-bit' : '32-bit';
 842          }
 843          if (MATH_BIGINTEGER_MODE != self::MODE_GMP && defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
 844              $opts[] = 'OpenSSL';
 845          }
 846          if (!empty($opts)) {
 847              $engine.= ' (' . implode('.', $opts) . ')';
 848          }
 849          return array(
 850              'value' => '0x' . $this->toHex(true),
 851              'engine' => $engine
 852          );
 853      }
 854  
 855      /**
 856       * Adds two BigIntegers.
 857       *
 858       * Here's an example:
 859       * <code>
 860       * <?php
 861       *    $a = new \phpseclib\Math\BigInteger('10');
 862       *    $b = new \phpseclib\Math\BigInteger('20');
 863       *
 864       *    $c = $a->add($b);
 865       *
 866       *    echo $c->toString(); // outputs 30
 867       * ?>
 868       * </code>
 869       *
 870       * @param \phpseclib\Math\BigInteger $y
 871       * @return \phpseclib\Math\BigInteger
 872       * @access public
 873       * @internal Performs base-2**52 addition
 874       */
 875      function add($y)
 876      {
 877          switch (MATH_BIGINTEGER_MODE) {
 878              case self::MODE_GMP:
 879                  $temp = new static();
 880                  $temp->value = gmp_add($this->value, $y->value);
 881  
 882                  return $this->_normalize($temp);
 883              case self::MODE_BCMATH:
 884                  $temp = new static();
 885                  $temp->value = bcadd($this->value, $y->value, 0);
 886  
 887                  return $this->_normalize($temp);
 888          }
 889  
 890          $temp = $this->_add($this->value, $this->is_negative, $y->value, $y->is_negative);
 891  
 892          $result = new static();
 893          $result->value = $temp[self::VALUE];
 894          $result->is_negative = $temp[self::SIGN];
 895  
 896          return $this->_normalize($result);
 897      }
 898  
 899      /**
 900       * Performs addition.
 901       *
 902       * @param array $x_value
 903       * @param bool $x_negative
 904       * @param array $y_value
 905       * @param bool $y_negative
 906       * @return array
 907       * @access private
 908       */
 909      function _add($x_value, $x_negative, $y_value, $y_negative)
 910      {
 911          $x_size = count($x_value);
 912          $y_size = count($y_value);
 913  
 914          if ($x_size == 0) {
 915              return array(
 916                  self::VALUE => $y_value,
 917                  self::SIGN => $y_negative
 918              );
 919          } elseif ($y_size == 0) {
 920              return array(
 921                  self::VALUE => $x_value,
 922                  self::SIGN => $x_negative
 923              );
 924          }
 925  
 926          // subtract, if appropriate
 927          if ($x_negative != $y_negative) {
 928              if ($x_value == $y_value) {
 929                  return array(
 930                      self::VALUE => array(),
 931                      self::SIGN => false
 932                  );
 933              }
 934  
 935              $temp = $this->_subtract($x_value, false, $y_value, false);
 936              $temp[self::SIGN] = $this->_compare($x_value, false, $y_value, false) > 0 ?
 937                                            $x_negative : $y_negative;
 938  
 939              return $temp;
 940          }
 941  
 942          if ($x_size < $y_size) {
 943              $size = $x_size;
 944              $value = $y_value;
 945          } else {
 946              $size = $y_size;
 947              $value = $x_value;
 948          }
 949  
 950          $value[count($value)] = 0; // just in case the carry adds an extra digit
 951  
 952          $carry = 0;
 953          for ($i = 0, $j = 1; $j < $size; $i+=2, $j+=2) {
 954              $sum = $x_value[$j] * self::$baseFull + $x_value[$i] + $y_value[$j] * self::$baseFull + $y_value[$i] + $carry;
 955              $carry = $sum >= self::$maxDigit2; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1
 956              $sum = $carry ? $sum - self::$maxDigit2 : $sum;
 957  
 958              $temp = self::$base === 26 ? intval($sum / 0x4000000) : ($sum >> 31);
 959  
 960              $value[$i] = (int) ($sum - self::$baseFull * $temp); // eg. a faster alternative to fmod($sum, 0x4000000)
 961              $value[$j] = $temp;
 962          }
 963  
 964          if ($j == $size) { // ie. if $y_size is odd
 965              $sum = $x_value[$i] + $y_value[$i] + $carry;
 966              $carry = $sum >= self::$baseFull;
 967              $value[$i] = $carry ? $sum - self::$baseFull : $sum;
 968              ++$i; // ie. let $i = $j since we've just done $value[$i]
 969          }
 970  
 971          if ($carry) {
 972              for (; $value[$i] == self::$maxDigit; ++$i) {
 973                  $value[$i] = 0;
 974              }
 975              ++$value[$i];
 976          }
 977  
 978          return array(
 979              self::VALUE => $this->_trim($value),
 980              self::SIGN => $x_negative
 981          );
 982      }
 983  
 984      /**
 985       * Subtracts two BigIntegers.
 986       *
 987       * Here's an example:
 988       * <code>
 989       * <?php
 990       *    $a = new \phpseclib\Math\BigInteger('10');
 991       *    $b = new \phpseclib\Math\BigInteger('20');
 992       *
 993       *    $c = $a->subtract($b);
 994       *
 995       *    echo $c->toString(); // outputs -10
 996       * ?>
 997       * </code>
 998       *
 999       * @param \phpseclib\Math\BigInteger $y
1000       * @return \phpseclib\Math\BigInteger
1001       * @access public
1002       * @internal Performs base-2**52 subtraction
1003       */
1004      function subtract($y)
1005      {
1006          switch (MATH_BIGINTEGER_MODE) {
1007              case self::MODE_GMP:
1008                  $temp = new static();
1009                  $temp->value = gmp_sub($this->value, $y->value);
1010  
1011                  return $this->_normalize($temp);
1012              case self::MODE_BCMATH:
1013                  $temp = new static();
1014                  $temp->value = bcsub($this->value, $y->value, 0);
1015  
1016                  return $this->_normalize($temp);
1017          }
1018  
1019          $temp = $this->_subtract($this->value, $this->is_negative, $y->value, $y->is_negative);
1020  
1021          $result = new static();
1022          $result->value = $temp[self::VALUE];
1023          $result->is_negative = $temp[self::SIGN];
1024  
1025          return $this->_normalize($result);
1026      }
1027  
1028      /**
1029       * Performs subtraction.
1030       *
1031       * @param array $x_value
1032       * @param bool $x_negative
1033       * @param array $y_value
1034       * @param bool $y_negative
1035       * @return array
1036       * @access private
1037       */
1038      function _subtract($x_value, $x_negative, $y_value, $y_negative)
1039      {
1040          $x_size = count($x_value);
1041          $y_size = count($y_value);
1042  
1043          if ($x_size == 0) {
1044              return array(
1045                  self::VALUE => $y_value,
1046                  self::SIGN => !$y_negative
1047              );
1048          } elseif ($y_size == 0) {
1049              return array(
1050                  self::VALUE => $x_value,
1051                  self::SIGN => $x_negative
1052              );
1053          }
1054  
1055          // add, if appropriate (ie. -$x - +$y or +$x - -$y)
1056          if ($x_negative != $y_negative) {
1057              $temp = $this->_add($x_value, false, $y_value, false);
1058              $temp[self::SIGN] = $x_negative;
1059  
1060              return $temp;
1061          }
1062  
1063          $diff = $this->_compare($x_value, $x_negative, $y_value, $y_negative);
1064  
1065          if (!$diff) {
1066              return array(
1067                  self::VALUE => array(),
1068                  self::SIGN => false
1069              );
1070          }
1071  
1072          // switch $x and $y around, if appropriate.
1073          if ((!$x_negative && $diff < 0) || ($x_negative && $diff > 0)) {
1074              $temp = $x_value;
1075              $x_value = $y_value;
1076              $y_value = $temp;
1077  
1078              $x_negative = !$x_negative;
1079  
1080              $x_size = count($x_value);
1081              $y_size = count($y_value);
1082          }
1083  
1084          // at this point, $x_value should be at least as big as - if not bigger than - $y_value
1085  
1086          $carry = 0;
1087          for ($i = 0, $j = 1; $j < $y_size; $i+=2, $j+=2) {
1088              $sum = $x_value[$j] * self::$baseFull + $x_value[$i] - $y_value[$j] * self::$baseFull - $y_value[$i] - $carry;
1089              $carry = $sum < 0; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1
1090              $sum = $carry ? $sum + self::$maxDigit2 : $sum;
1091  
1092              $temp = self::$base === 26 ? intval($sum / 0x4000000) : ($sum >> 31);
1093  
1094              $x_value[$i] = (int) ($sum - self::$baseFull * $temp);
1095              $x_value[$j] = $temp;
1096          }
1097  
1098          if ($j == $y_size) { // ie. if $y_size is odd
1099              $sum = $x_value[$i] - $y_value[$i] - $carry;
1100              $carry = $sum < 0;
1101              $x_value[$i] = $carry ? $sum + self::$baseFull : $sum;
1102              ++$i;
1103          }
1104  
1105          if ($carry) {
1106              for (; !$x_value[$i]; ++$i) {
1107                  $x_value[$i] = self::$maxDigit;
1108              }
1109              --$x_value[$i];
1110          }
1111  
1112          return array(
1113              self::VALUE => $this->_trim($x_value),
1114              self::SIGN => $x_negative
1115          );
1116      }
1117  
1118      /**
1119       * Multiplies two BigIntegers
1120       *
1121       * Here's an example:
1122       * <code>
1123       * <?php
1124       *    $a = new \phpseclib\Math\BigInteger('10');
1125       *    $b = new \phpseclib\Math\BigInteger('20');
1126       *
1127       *    $c = $a->multiply($b);
1128       *
1129       *    echo $c->toString(); // outputs 200
1130       * ?>
1131       * </code>
1132       *
1133       * @param \phpseclib\Math\BigInteger $x
1134       * @return \phpseclib\Math\BigInteger
1135       * @access public
1136       */
1137      function multiply($x)
1138      {
1139          switch (MATH_BIGINTEGER_MODE) {
1140              case self::MODE_GMP:
1141                  $temp = new static();
1142                  $temp->value = gmp_mul($this->value, $x->value);
1143  
1144                  return $this->_normalize($temp);
1145              case self::MODE_BCMATH:
1146                  $temp = new static();
1147                  $temp->value = bcmul($this->value, $x->value, 0);
1148  
1149                  return $this->_normalize($temp);
1150          }
1151  
1152          $temp = $this->_multiply($this->value, $this->is_negative, $x->value, $x->is_negative);
1153  
1154          $product = new static();
1155          $product->value = $temp[self::VALUE];
1156          $product->is_negative = $temp[self::SIGN];
1157  
1158          return $this->_normalize($product);
1159      }
1160  
1161      /**
1162       * Performs multiplication.
1163       *
1164       * @param array $x_value
1165       * @param bool $x_negative
1166       * @param array $y_value
1167       * @param bool $y_negative
1168       * @return array
1169       * @access private
1170       */
1171      function _multiply($x_value, $x_negative, $y_value, $y_negative)
1172      {
1173          //if ( $x_value == $y_value ) {
1174          //    return array(
1175          //        self::VALUE => $this->_square($x_value),
1176          //        self::SIGN => $x_sign != $y_value
1177          //    );
1178          //}
1179  
1180          $x_length = count($x_value);
1181          $y_length = count($y_value);
1182  
1183          if (!$x_length || !$y_length) { // a 0 is being multiplied
1184              return array(
1185                  self::VALUE => array(),
1186                  self::SIGN => false
1187              );
1188          }
1189  
1190          return array(
1191              self::VALUE => min($x_length, $y_length) < 2 * self::KARATSUBA_CUTOFF ?
1192                  $this->_trim($this->_regularMultiply($x_value, $y_value)) :
1193                  $this->_trim($this->_karatsuba($x_value, $y_value)),
1194              self::SIGN => $x_negative != $y_negative
1195          );
1196      }
1197  
1198      /**
1199       * Performs long multiplication on two BigIntegers
1200       *
1201       * Modeled after 'multiply' in MutableBigInteger.java.
1202       *
1203       * @param array $x_value
1204       * @param array $y_value
1205       * @return array
1206       * @access private
1207       */
1208      function _regularMultiply($x_value, $y_value)
1209      {
1210          $x_length = count($x_value);
1211          $y_length = count($y_value);
1212  
1213          if (!$x_length || !$y_length) { // a 0 is being multiplied
1214              return array();
1215          }
1216  
1217          if ($x_length < $y_length) {
1218              $temp = $x_value;
1219              $x_value = $y_value;
1220              $y_value = $temp;
1221  
1222              $x_length = count($x_value);
1223              $y_length = count($y_value);
1224          }
1225  
1226          $product_value = $this->_array_repeat(0, $x_length + $y_length);
1227  
1228          // the following for loop could be removed if the for loop following it
1229          // (the one with nested for loops) initially set $i to 0, but
1230          // doing so would also make the result in one set of unnecessary adds,
1231          // since on the outermost loops first pass, $product->value[$k] is going
1232          // to always be 0
1233  
1234          $carry = 0;
1235  
1236          for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0
1237              $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0
1238              $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
1239              $product_value[$j] = (int) ($temp - self::$baseFull * $carry);
1240          }
1241  
1242          $product_value[$j] = $carry;
1243  
1244          // the above for loop is what the previous comment was talking about.  the
1245          // following for loop is the "one with nested for loops"
1246          for ($i = 1; $i < $y_length; ++$i) {
1247              $carry = 0;
1248  
1249              for ($j = 0, $k = $i; $j < $x_length; ++$j, ++$k) {
1250                  $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry;
1251                  $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
1252                  $product_value[$k] = (int) ($temp - self::$baseFull * $carry);
1253              }
1254  
1255              $product_value[$k] = $carry;
1256          }
1257  
1258          return $product_value;
1259      }
1260  
1261      /**
1262       * Performs Karatsuba multiplication on two BigIntegers
1263       *
1264       * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and
1265       * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=120 MPM 5.2.3}.
1266       *
1267       * @param array $x_value
1268       * @param array $y_value
1269       * @return array
1270       * @access private
1271       */
1272      function _karatsuba($x_value, $y_value)
1273      {
1274          $m = min(count($x_value) >> 1, count($y_value) >> 1);
1275  
1276          if ($m < self::KARATSUBA_CUTOFF) {
1277              return $this->_regularMultiply($x_value, $y_value);
1278          }
1279  
1280          $x1 = array_slice($x_value, $m);
1281          $x0 = array_slice($x_value, 0, $m);
1282          $y1 = array_slice($y_value, $m);
1283          $y0 = array_slice($y_value, 0, $m);
1284  
1285          $z2 = $this->_karatsuba($x1, $y1);
1286          $z0 = $this->_karatsuba($x0, $y0);
1287  
1288          $z1 = $this->_add($x1, false, $x0, false);
1289          $temp = $this->_add($y1, false, $y0, false);
1290          $z1 = $this->_karatsuba($z1[self::VALUE], $temp[self::VALUE]);
1291          $temp = $this->_add($z2, false, $z0, false);
1292          $z1 = $this->_subtract($z1, false, $temp[self::VALUE], false);
1293  
1294          $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2);
1295          $z1[self::VALUE] = array_merge(array_fill(0, $m, 0), $z1[self::VALUE]);
1296  
1297          $xy = $this->_add($z2, false, $z1[self::VALUE], $z1[self::SIGN]);
1298          $xy = $this->_add($xy[self::VALUE], $xy[self::SIGN], $z0, false);
1299  
1300          return $xy[self::VALUE];
1301      }
1302  
1303      /**
1304       * Performs squaring
1305       *
1306       * @param array $x
1307       * @return array
1308       * @access private
1309       */
1310      function _square($x = false)
1311      {
1312          return count($x) < 2 * self::KARATSUBA_CUTOFF ?
1313              $this->_trim($this->_baseSquare($x)) :
1314              $this->_trim($this->_karatsubaSquare($x));
1315      }
1316  
1317      /**
1318       * Performs traditional squaring on two BigIntegers
1319       *
1320       * Squaring can be done faster than multiplying a number by itself can be.  See
1321       * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=7 HAC 14.2.4} /
1322       * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=141 MPM 5.3} for more information.
1323       *
1324       * @param array $value
1325       * @return array
1326       * @access private
1327       */
1328      function _baseSquare($value)
1329      {
1330          if (empty($value)) {
1331              return array();
1332          }
1333          $square_value = $this->_array_repeat(0, 2 * count($value));
1334  
1335          for ($i = 0, $max_index = count($value) - 1; $i <= $max_index; ++$i) {
1336              $i2 = $i << 1;
1337  
1338              $temp = $square_value[$i2] + $value[$i] * $value[$i];
1339              $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
1340              $square_value[$i2] = (int) ($temp - self::$baseFull * $carry);
1341  
1342              // note how we start from $i+1 instead of 0 as we do in multiplication.
1343              for ($j = $i + 1, $k = $i2 + 1; $j <= $max_index; ++$j, ++$k) {
1344                  $temp = $square_value[$k] + 2 * $value[$j] * $value[$i] + $carry;
1345                  $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
1346                  $square_value[$k] = (int) ($temp - self::$baseFull * $carry);
1347              }
1348  
1349              // the following line can yield values larger 2**15.  at this point, PHP should switch
1350              // over to floats.
1351              $square_value[$i + $max_index + 1] = $carry;
1352          }
1353  
1354          return $square_value;
1355      }
1356  
1357      /**
1358       * Performs Karatsuba "squaring" on two BigIntegers
1359       *
1360       * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and
1361       * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=151 MPM 5.3.4}.
1362       *
1363       * @param array $value
1364       * @return array
1365       * @access private
1366       */
1367      function _karatsubaSquare($value)
1368      {
1369          $m = count($value) >> 1;
1370  
1371          if ($m < self::KARATSUBA_CUTOFF) {
1372              return $this->_baseSquare($value);
1373          }
1374  
1375          $x1 = array_slice($value, $m);
1376          $x0 = array_slice($value, 0, $m);
1377  
1378          $z2 = $this->_karatsubaSquare($x1);
1379          $z0 = $this->_karatsubaSquare($x0);
1380  
1381          $z1 = $this->_add($x1, false, $x0, false);
1382          $z1 = $this->_karatsubaSquare($z1[self::VALUE]);
1383          $temp = $this->_add($z2, false, $z0, false);
1384          $z1 = $this->_subtract($z1, false, $temp[self::VALUE], false);
1385  
1386          $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2);
1387          $z1[self::VALUE] = array_merge(array_fill(0, $m, 0), $z1[self::VALUE]);
1388  
1389          $xx = $this->_add($z2, false, $z1[self::VALUE], $z1[self::SIGN]);
1390          $xx = $this->_add($xx[self::VALUE], $xx[self::SIGN], $z0, false);
1391  
1392          return $xx[self::VALUE];
1393      }
1394  
1395      /**
1396       * Divides two BigIntegers.
1397       *
1398       * Returns an array whose first element contains the quotient and whose second element contains the
1399       * "common residue".  If the remainder would be positive, the "common residue" and the remainder are the
1400       * same.  If the remainder would be negative, the "common residue" is equal to the sum of the remainder
1401       * and the divisor (basically, the "common residue" is the first positive modulo).
1402       *
1403       * Here's an example:
1404       * <code>
1405       * <?php
1406       *    $a = new \phpseclib\Math\BigInteger('10');
1407       *    $b = new \phpseclib\Math\BigInteger('20');
1408       *
1409       *    list($quotient, $remainder) = $a->divide($b);
1410       *
1411       *    echo $quotient->toString(); // outputs 0
1412       *    echo "\r\n";
1413       *    echo $remainder->toString(); // outputs 10
1414       * ?>
1415       * </code>
1416       *
1417       * @param \phpseclib\Math\BigInteger $y
1418       * @return array
1419       * @access public
1420       * @internal This function is based off of {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=9 HAC 14.20}.
1421       */
1422      function divide($y)
1423      {
1424          switch (MATH_BIGINTEGER_MODE) {
1425              case self::MODE_GMP:
1426                  $quotient = new static();
1427                  $remainder = new static();
1428  
1429                  list($quotient->value, $remainder->value) = gmp_div_qr($this->value, $y->value);
1430  
1431                  if (gmp_sign($remainder->value) < 0) {
1432                      $remainder->value = gmp_add($remainder->value, gmp_abs($y->value));
1433                  }
1434  
1435                  return array($this->_normalize($quotient), $this->_normalize($remainder));
1436              case self::MODE_BCMATH:
1437                  $quotient = new static();
1438                  $remainder = new static();
1439  
1440                  $quotient->value = bcdiv($this->value, $y->value, 0);
1441                  $remainder->value = bcmod($this->value, $y->value);
1442  
1443                  if ($remainder->value[0] == '-') {
1444                      $remainder->value = bcadd($remainder->value, $y->value[0] == '-' ? substr($y->value, 1) : $y->value, 0);
1445                  }
1446  
1447                  return array($this->_normalize($quotient), $this->_normalize($remainder));
1448          }
1449  
1450          if (count($y->value) == 1) {
1451              list($q, $r) = $this->_divide_digit($this->value, $y->value[0]);
1452              $quotient = new static();
1453              $remainder = new static();
1454              $quotient->value = $q;
1455              $remainder->value = array($r);
1456              $quotient->is_negative = $this->is_negative != $y->is_negative;
1457              return array($this->_normalize($quotient), $this->_normalize($remainder));
1458          }
1459  
1460          static $zero;
1461          if (!isset($zero)) {
1462              $zero = new static();
1463          }
1464  
1465          $x = $this->copy();
1466          $y = $y->copy();
1467  
1468          $x_sign = $x->is_negative;
1469          $y_sign = $y->is_negative;
1470  
1471          $x->is_negative = $y->is_negative = false;
1472  
1473          $diff = $x->compare($y);
1474  
1475          if (!$diff) {
1476              $temp = new static();
1477              $temp->value = array(1);
1478              $temp->is_negative = $x_sign != $y_sign;
1479              return array($this->_normalize($temp), $this->_normalize(new static()));
1480          }
1481  
1482          if ($diff < 0) {
1483              // if $x is negative, "add" $y.
1484              if ($x_sign) {
1485                  $x = $y->subtract($x);
1486              }
1487              return array($this->_normalize(new static()), $this->_normalize($x));
1488          }
1489  
1490          // normalize $x and $y as described in HAC 14.23 / 14.24
1491          $msb = $y->value[count($y->value) - 1];
1492          for ($shift = 0; !($msb & self::$msb); ++$shift) {
1493              $msb <<= 1;
1494          }
1495          $x->_lshift($shift);
1496          $y->_lshift($shift);
1497          $y_value = &$y->value;
1498  
1499          $x_max = count($x->value) - 1;
1500          $y_max = count($y->value) - 1;
1501  
1502          $quotient = new static();
1503          $quotient_value = &$quotient->value;
1504          $quotient_value = $this->_array_repeat(0, $x_max - $y_max + 1);
1505  
1506          static $temp, $lhs, $rhs;
1507          if (!isset($temp)) {
1508              $temp = new static();
1509              $lhs =  new static();
1510              $rhs =  new static();
1511          }
1512          $temp_value = &$temp->value;
1513          $rhs_value =  &$rhs->value;
1514  
1515          // $temp = $y << ($x_max - $y_max-1) in base 2**26
1516          $temp_value = array_merge($this->_array_repeat(0, $x_max - $y_max), $y_value);
1517  
1518          while ($x->compare($temp) >= 0) {
1519              // calculate the "common residue"
1520              ++$quotient_value[$x_max - $y_max];
1521              $x = $x->subtract($temp);
1522              $x_max = count($x->value) - 1;
1523          }
1524  
1525          for ($i = $x_max; $i >= $y_max + 1; --$i) {
1526              $x_value = &$x->value;
1527              $x_window = array(
1528                  isset($x_value[$i]) ? $x_value[$i] : 0,
1529                  isset($x_value[$i - 1]) ? $x_value[$i - 1] : 0,
1530                  isset($x_value[$i - 2]) ? $x_value[$i - 2] : 0
1531              );
1532              $y_window = array(
1533                  $y_value[$y_max],
1534                  ($y_max > 0) ? $y_value[$y_max - 1] : 0
1535              );
1536  
1537              $q_index = $i - $y_max - 1;
1538              if ($x_window[0] == $y_window[0]) {
1539                  $quotient_value[$q_index] = self::$maxDigit;
1540              } else {
1541                  $quotient_value[$q_index] = $this->_safe_divide(
1542                      $x_window[0] * self::$baseFull + $x_window[1],
1543                      $y_window[0]
1544                  );
1545              }
1546  
1547              $temp_value = array($y_window[1], $y_window[0]);
1548  
1549              $lhs->value = array($quotient_value[$q_index]);
1550              $lhs = $lhs->multiply($temp);
1551  
1552              $rhs_value = array($x_window[2], $x_window[1], $x_window[0]);
1553  
1554              while ($lhs->compare($rhs) > 0) {
1555                  --$quotient_value[$q_index];
1556  
1557                  $lhs->value = array($quotient_value[$q_index]);
1558                  $lhs = $lhs->multiply($temp);
1559              }
1560  
1561              $adjust = $this->_array_repeat(0, $q_index);
1562              $temp_value = array($quotient_value[$q_index]);
1563              $temp = $temp->multiply($y);
1564              $temp_value = &$temp->value;
1565              if (count($temp_value)) {
1566                  $temp_value = array_merge($adjust, $temp_value);
1567              }
1568  
1569              $x = $x->subtract($temp);
1570  
1571              if ($x->compare($zero) < 0) {
1572                  $temp_value = array_merge($adjust, $y_value);
1573                  $x = $x->add($temp);
1574  
1575                  --$quotient_value[$q_index];
1576              }
1577  
1578              $x_max = count($x_value) - 1;
1579          }
1580  
1581          // unnormalize the remainder
1582          $x->_rshift($shift);
1583  
1584          $quotient->is_negative = $x_sign != $y_sign;
1585  
1586          // calculate the "common residue", if appropriate
1587          if ($x_sign) {
1588              $y->_rshift($shift);
1589              $x = $y->subtract($x);
1590          }
1591  
1592          return array($this->_normalize($quotient), $this->_normalize($x));
1593      }
1594  
1595      /**
1596       * Divides a BigInteger by a regular integer
1597       *
1598       * abc / x = a00 / x + b0 / x + c / x
1599       *
1600       * @param array $dividend
1601       * @param array $divisor
1602       * @return array
1603       * @access private
1604       */
1605      function _divide_digit($dividend, $divisor)
1606      {
1607          $carry = 0;
1608          $result = array();
1609  
1610          for ($i = count($dividend) - 1; $i >= 0; --$i) {
1611              $temp = self::$baseFull * $carry + $dividend[$i];
1612              $result[$i] = $this->_safe_divide($temp, $divisor);
1613              $carry = (int) ($temp - $divisor * $result[$i]);
1614          }
1615  
1616          return array($result, $carry);
1617      }
1618  
1619      /**
1620       * Performs modular exponentiation.
1621       *
1622       * Here's an example:
1623       * <code>
1624       * <?php
1625       *    $a = new \phpseclib\Math\BigInteger('10');
1626       *    $b = new \phpseclib\Math\BigInteger('20');
1627       *    $c = new \phpseclib\Math\BigInteger('30');
1628       *
1629       *    $c = $a->modPow($b, $c);
1630       *
1631       *    echo $c->toString(); // outputs 10
1632       * ?>
1633       * </code>
1634       *
1635       * @param \phpseclib\Math\BigInteger $e
1636       * @param \phpseclib\Math\BigInteger $n
1637       * @return \phpseclib\Math\BigInteger
1638       * @access public
1639       * @internal The most naive approach to modular exponentiation has very unreasonable requirements, and
1640       *    and although the approach involving repeated squaring does vastly better, it, too, is impractical
1641       *    for our purposes.  The reason being that division - by far the most complicated and time-consuming
1642       *    of the basic operations (eg. +,-,*,/) - occurs multiple times within it.
1643       *
1644       *    Modular reductions resolve this issue.  Although an individual modular reduction takes more time
1645       *    then an individual division, when performed in succession (with the same modulo), they're a lot faster.
1646       *
1647       *    The two most commonly used modular reductions are Barrett and Montgomery reduction.  Montgomery reduction,
1648       *    although faster, only works when the gcd of the modulo and of the base being used is 1.  In RSA, when the
1649       *    base is a power of two, the modulo - a product of two primes - is always going to have a gcd of 1 (because
1650       *    the product of two odd numbers is odd), but what about when RSA isn't used?
1651       *
1652       *    In contrast, Barrett reduction has no such constraint.  As such, some bigint implementations perform a
1653       *    Barrett reduction after every operation in the modpow function.  Others perform Barrett reductions when the
1654       *    modulo is even and Montgomery reductions when the modulo is odd.  BigInteger.java's modPow method, however,
1655       *    uses a trick involving the Chinese Remainder Theorem to factor the even modulo into two numbers - one odd and
1656       *    the other, a power of two - and recombine them, later.  This is the method that this modPow function uses.
1657       *    {@link http://islab.oregonstate.edu/papers/j34monex.pdf Montgomery Reduction with Even Modulus} elaborates.
1658       */
1659      function modPow($e, $n)
1660      {
1661          $n = $this->bitmask !== false && $this->bitmask->compare($n) < 0 ? $this->bitmask : $n->abs();
1662  
1663          if ($e->compare(new static()) < 0) {
1664              $e = $e->abs();
1665  
1666              $temp = $this->modInverse($n);
1667              if ($temp === false) {
1668                  return false;
1669              }
1670  
1671              return $this->_normalize($temp->modPow($e, $n));
1672          }
1673  
1674          if (MATH_BIGINTEGER_MODE == self::MODE_GMP) {
1675              $temp = new static();
1676              $temp->value = gmp_powm($this->value, $e->value, $n->value);
1677  
1678              return $this->_normalize($temp);
1679          }
1680  
1681          if ($this->compare(new static()) < 0 || $this->compare($n) > 0) {
1682              list(, $temp) = $this->divide($n);
1683              return $temp->modPow($e, $n);
1684          }
1685  
1686          if (defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
1687              $components = array(
1688                  'modulus' => $n->toBytes(true),
1689                  'publicExponent' => $e->toBytes(true)
1690              );
1691  
1692              $components = array(
1693                  'modulus' => pack('Ca*a*', 2, $this->_encodeASN1Length(strlen($components['modulus'])), $components['modulus']),
1694                  'publicExponent' => pack('Ca*a*', 2, $this->_encodeASN1Length(strlen($components['publicExponent'])), $components['publicExponent'])
1695              );
1696  
1697              $RSAPublicKey = pack(
1698                  'Ca*a*a*',
1699                  48,
1700                  $this->_encodeASN1Length(strlen($components['modulus']) + strlen($components['publicExponent'])),
1701                  $components['modulus'],
1702                  $components['publicExponent']
1703              );
1704  
1705              $rsaOID = pack('H*', '300d06092a864886f70d0101010500'); // hex version of MA0GCSqGSIb3DQEBAQUA
1706              $RSAPublicKey = chr(0) . $RSAPublicKey;
1707              $RSAPublicKey = chr(3) . $this->_encodeASN1Length(strlen($RSAPublicKey)) . $RSAPublicKey;
1708  
1709              $encapsulated = pack(
1710                  'Ca*a*',
1711                  48,
1712                  $this->_encodeASN1Length(strlen($rsaOID . $RSAPublicKey)),
1713                  $rsaOID . $RSAPublicKey
1714              );
1715  
1716              $RSAPublicKey = "-----BEGIN PUBLIC KEY-----\r\n" .
1717                               chunk_split(base64_encode($encapsulated)) .
1718                               '-----END PUBLIC KEY-----';
1719  
1720              $plaintext = str_pad($this->toBytes(), strlen($n->toBytes(true)) - 1, "\0", STR_PAD_LEFT);
1721  
1722              if (openssl_public_encrypt($plaintext, $result, $RSAPublicKey, OPENSSL_NO_PADDING)) {
1723                  return new static($result, 256);
1724              }
1725          }
1726  
1727          if (MATH_BIGINTEGER_MODE == self::MODE_BCMATH) {
1728              $temp = new static();
1729              $temp->value = bcpowmod($this->value, $e->value, $n->value, 0);
1730  
1731              return $this->_normalize($temp);
1732          }
1733  
1734          if (empty($e->value)) {
1735              $temp = new static();
1736              $temp->value = array(1);
1737              return $this->_normalize($temp);
1738          }
1739  
1740          if ($e->value == array(1)) {
1741              list(, $temp) = $this->divide($n);
1742              return $this->_normalize($temp);
1743          }
1744  
1745          if ($e->value == array(2)) {
1746              $temp = new static();
1747              $temp->value = $this->_square($this->value);
1748              list(, $temp) = $temp->divide($n);
1749              return $this->_normalize($temp);
1750          }
1751  
1752          return $this->_normalize($this->_slidingWindow($e, $n, self::BARRETT));
1753  
1754          // the following code, although not callable, can be run independently of the above code
1755          // although the above code performed better in my benchmarks the following could might
1756          // perform better under different circumstances. in lieu of deleting it it's just been
1757          // made uncallable
1758  
1759          // is the modulo odd?
1760          if ($n->value[0] & 1) {
1761              return $this->_normalize($this->_slidingWindow($e, $n, self::MONTGOMERY));
1762          }
1763          // if it's not, it's even
1764  
1765          // find the lowest set bit (eg. the max pow of 2 that divides $n)
1766          for ($i = 0; $i < count($n->value); ++$i) {
1767              if ($n->value[$i]) {
1768                  $temp = decbin($n->value[$i]);
1769                  $j = strlen($temp) - strrpos($temp, '1') - 1;
1770                  $j+= 26 * $i;
1771                  break;
1772              }
1773          }
1774          // at this point, 2^$j * $n/(2^$j) == $n
1775  
1776          $mod1 = $n->copy();
1777          $mod1->_rshift($j);
1778          $mod2 = new static();
1779          $mod2->value = array(1);
1780          $mod2->_lshift($j);
1781  
1782          $part1 = ($mod1->value != array(1)) ? $this->_slidingWindow($e, $mod1, self::MONTGOMERY) : new static();
1783          $part2 = $this->_slidingWindow($e, $mod2, self::POWEROF2);
1784  
1785          $y1 = $mod2->modInverse($mod1);
1786          $y2 = $mod1->modInverse($mod2);
1787  
1788          $result = $part1->multiply($mod2);
1789          $result = $result->multiply($y1);
1790  
1791          $temp = $part2->multiply($mod1);
1792          $temp = $temp->multiply($y2);
1793  
1794          $result = $result->add($temp);
1795          list(, $result) = $result->divide($n);
1796  
1797          return $this->_normalize($result);
1798      }
1799  
1800      /**
1801       * Performs modular exponentiation.
1802       *
1803       * Alias for modPow().
1804       *
1805       * @param \phpseclib\Math\BigInteger $e
1806       * @param \phpseclib\Math\BigInteger $n
1807       * @return \phpseclib\Math\BigInteger
1808       * @access public
1809       */
1810      function powMod($e, $n)
1811      {
1812          return $this->modPow($e, $n);
1813      }
1814  
1815      /**
1816       * Sliding Window k-ary Modular Exponentiation
1817       *
1818       * Based on {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=27 HAC 14.85} /
1819       * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=210 MPM 7.7}.  In a departure from those algorithims,
1820       * however, this function performs a modular reduction after every multiplication and squaring operation.
1821       * As such, this function has the same preconditions that the reductions being used do.
1822       *
1823       * @param \phpseclib\Math\BigInteger $e
1824       * @param \phpseclib\Math\BigInteger $n
1825       * @param int $mode
1826       * @return \phpseclib\Math\BigInteger
1827       * @access private
1828       */
1829      function _slidingWindow($e, $n, $mode)
1830      {
1831          static $window_ranges = array(7, 25, 81, 241, 673, 1793); // from BigInteger.java's oddModPow function
1832          //static $window_ranges = array(0, 7, 36, 140, 450, 1303, 3529); // from MPM 7.3.1
1833  
1834          $e_value = $e->value;
1835          $e_length = count($e_value) - 1;
1836          $e_bits = decbin($e_value[$e_length]);
1837          for ($i = $e_length - 1; $i >= 0; --$i) {
1838              $e_bits.= str_pad(decbin($e_value[$i]), self::$base, '0', STR_PAD_LEFT);
1839          }
1840  
1841          $e_length = strlen($e_bits);
1842  
1843          // calculate the appropriate window size.
1844          // $window_size == 3 if $window_ranges is between 25 and 81, for example.
1845          for ($i = 0, $window_size = 1; $i < count($window_ranges) && $e_length > $window_ranges[$i]; ++$window_size, ++$i) {
1846          }
1847  
1848          $n_value = $n->value;
1849  
1850          // precompute $this^0 through $this^$window_size
1851          $powers = array();
1852          $powers[1] = $this->_prepareReduce($this->value, $n_value, $mode);
1853          $powers[2] = $this->_squareReduce($powers[1], $n_value, $mode);
1854  
1855          // we do every other number since substr($e_bits, $i, $j+1) (see below) is supposed to end
1856          // in a 1.  ie. it's supposed to be odd.
1857          $temp = 1 << ($window_size - 1);
1858          for ($i = 1; $i < $temp; ++$i) {
1859              $i2 = $i << 1;
1860              $powers[$i2 + 1] = $this->_multiplyReduce($powers[$i2 - 1], $powers[2], $n_value, $mode);
1861          }
1862  
1863          $result = array(1);
1864          $result = $this->_prepareReduce($result, $n_value, $mode);
1865  
1866          for ($i = 0; $i < $e_length;) {
1867              if (!$e_bits[$i]) {
1868                  $result = $this->_squareReduce($result, $n_value, $mode);
1869                  ++$i;
1870              } else {
1871                  for ($j = $window_size - 1; $j > 0; --$j) {
1872                      if (!empty($e_bits[$i + $j])) {
1873                          break;
1874                      }
1875                  }
1876  
1877                  // eg. the length of substr($e_bits, $i, $j + 1)
1878                  for ($k = 0; $k <= $j; ++$k) {
1879                      $result = $this->_squareReduce($result, $n_value, $mode);
1880                  }
1881  
1882                  $result = $this->_multiplyReduce($result, $powers[bindec(substr($e_bits, $i, $j + 1))], $n_value, $mode);
1883  
1884                  $i += $j + 1;
1885              }
1886          }
1887  
1888          $temp = new static();
1889          $temp->value = $this->_reduce($result, $n_value, $mode);
1890  
1891          return $temp;
1892      }
1893  
1894      /**
1895       * Modular reduction
1896       *
1897       * For most $modes this will return the remainder.
1898       *
1899       * @see self::_slidingWindow()
1900       * @access private
1901       * @param array $x
1902       * @param array $n
1903       * @param int $mode
1904       * @return array
1905       */
1906      function _reduce($x, $n, $mode)
1907      {
1908          switch ($mode) {
1909              case self::MONTGOMERY:
1910                  return $this->_montgomery($x, $n);
1911              case self::BARRETT:
1912                  return $this->_barrett($x, $n);
1913              case self::POWEROF2:
1914                  $lhs = new static();
1915                  $lhs->value = $x;
1916                  $rhs = new static();
1917                  $rhs->value = $n;
1918                  return $x->_mod2($n);
1919              case self::CLASSIC:
1920                  $lhs = new static();
1921                  $lhs->value = $x;
1922                  $rhs = new static();
1923                  $rhs->value = $n;
1924                  list(, $temp) = $lhs->divide($rhs);
1925                  return $temp->value;
1926              case self::NONE:
1927                  return $x;
1928              default:
1929                  // an invalid $mode was provided
1930          }
1931      }
1932  
1933      /**
1934       * Modular reduction preperation
1935       *
1936       * @see self::_slidingWindow()
1937       * @access private
1938       * @param array $x
1939       * @param array $n
1940       * @param int $mode
1941       * @return array
1942       */
1943      function _prepareReduce($x, $n, $mode)
1944      {
1945          if ($mode == self::MONTGOMERY) {
1946              return $this->_prepMontgomery($x, $n);
1947          }
1948          return $this->_reduce($x, $n, $mode);
1949      }
1950  
1951      /**
1952       * Modular multiply
1953       *
1954       * @see self::_slidingWindow()
1955       * @access private
1956       * @param array $x
1957       * @param array $y
1958       * @param array $n
1959       * @param int $mode
1960       * @return array
1961       */
1962      function _multiplyReduce($x, $y, $n, $mode)
1963      {
1964          if ($mode == self::MONTGOMERY) {
1965              return $this->_montgomeryMultiply($x, $y, $n);
1966          }
1967          $temp = $this->_multiply($x, false, $y, false);
1968          return $this->_reduce($temp[self::VALUE], $n, $mode);
1969      }
1970  
1971      /**
1972       * Modular square
1973       *
1974       * @see self::_slidingWindow()
1975       * @access private
1976       * @param array $x
1977       * @param array $n
1978       * @param int $mode
1979       * @return array
1980       */
1981      function _squareReduce($x, $n, $mode)
1982      {
1983          if ($mode == self::MONTGOMERY) {
1984              return $this->_montgomeryMultiply($x, $x, $n);
1985          }
1986          return $this->_reduce($this->_square($x), $n, $mode);
1987      }
1988  
1989      /**
1990       * Modulos for Powers of Two
1991       *
1992       * Calculates $x%$n, where $n = 2**$e, for some $e.  Since this is basically the same as doing $x & ($n-1),
1993       * we'll just use this function as a wrapper for doing that.
1994       *
1995       * @see self::_slidingWindow()
1996       * @access private
1997       * @param \phpseclib\Math\BigInteger $n
1998       * @return \phpseclib\Math\BigInteger
1999       */
2000      function _mod2($n)
2001      {
2002          $temp = new static();
2003          $temp->value = array(1);
2004          return $this->bitwise_and($n->subtract($temp));
2005      }
2006  
2007      /**
2008       * Barrett Modular Reduction
2009       *
2010       * See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=14 HAC 14.3.3} /
2011       * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=165 MPM 6.2.5} for more information.  Modified slightly,
2012       * so as not to require negative numbers (initially, this script didn't support negative numbers).
2013       *
2014       * Employs "folding", as described at
2015       * {@link http://www.cosic.esat.kuleuven.be/publications/thesis-149.pdf#page=66 thesis-149.pdf#page=66}.  To quote from
2016       * it, "the idea [behind folding] is to find a value x' such that x (mod m) = x' (mod m), with x' being smaller than x."
2017       *
2018       * Unfortunately, the "Barrett Reduction with Folding" algorithm described in thesis-149.pdf is not, as written, all that
2019       * usable on account of (1) its not using reasonable radix points as discussed in
2020       * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=162 MPM 6.2.2} and (2) the fact that, even with reasonable
2021       * radix points, it only works when there are an even number of digits in the denominator.  The reason for (2) is that
2022       * (x >> 1) + (x >> 1) != x / 2 + x / 2.  If x is even, they're the same, but if x is odd, they're not.  See the in-line
2023       * comments for details.
2024       *
2025       * @see self::_slidingWindow()
2026       * @access private
2027       * @param array $n
2028       * @param array $m
2029       * @return array
2030       */
2031      function _barrett($n, $m)
2032      {
2033          static $cache = array(
2034              self::VARIABLE => array(),
2035              self::DATA => array()
2036          );
2037  
2038          $m_length = count($m);
2039  
2040          // if ($this->_compare($n, $this->_square($m)) >= 0) {
2041          if (count($n) > 2 * $m_length) {
2042              $lhs = new static();
2043              $rhs = new static();
2044              $lhs->value = $n;
2045              $rhs->value = $m;
2046              list(, $temp) = $lhs->divide($rhs);
2047              return $temp->value;
2048          }
2049  
2050          // if (m.length >> 1) + 2 <= m.length then m is too small and n can't be reduced
2051          if ($m_length < 5) {
2052              return $this->_regularBarrett($n, $m);
2053          }
2054  
2055          // n = 2 * m.length
2056  
2057          if (($key = array_search($m, $cache[self::VARIABLE])) === false) {
2058              $key = count($cache[self::VARIABLE]);
2059              $cache[self::VARIABLE][] = $m;
2060  
2061              $lhs = new static();
2062              $lhs_value = &$lhs->value;
2063              $lhs_value = $this->_array_repeat(0, $m_length + ($m_length >> 1));
2064              $lhs_value[] = 1;
2065              $rhs = new static();
2066              $rhs->value = $m;
2067  
2068              list($u, $m1) = $lhs->divide($rhs);
2069              $u = $u->value;
2070              $m1 = $m1->value;
2071  
2072              $cache[self::DATA][] = array(
2073                  'u' => $u, // m.length >> 1 (technically (m.length >> 1) + 1)
2074                  'm1'=> $m1 // m.length
2075              );
2076          } else {
2077              extract($cache[self::DATA][$key]);
2078          }
2079  
2080          $cutoff = $m_length + ($m_length >> 1);
2081          $lsd = array_slice($n, 0, $cutoff); // m.length + (m.length >> 1)
2082          $msd = array_slice($n, $cutoff);    // m.length >> 1
2083          $lsd = $this->_trim($lsd);
2084          $temp = $this->_multiply($msd, false, $m1, false);
2085          $n = $this->_add($lsd, false, $temp[self::VALUE], false); // m.length + (m.length >> 1) + 1
2086  
2087          if ($m_length & 1) {
2088              return $this->_regularBarrett($n[self::VALUE], $m);
2089          }
2090  
2091          // (m.length + (m.length >> 1) + 1) - (m.length - 1) == (m.length >> 1) + 2
2092          $temp = array_slice($n[self::VALUE], $m_length - 1);
2093          // if even: ((m.length >> 1) + 2) + (m.length >> 1) == m.length + 2
2094          // if odd:  ((m.length >> 1) + 2) + (m.length >> 1) == (m.length - 1) + 2 == m.length + 1
2095          $temp = $this->_multiply($temp, false, $u, false);
2096          // if even: (m.length + 2) - ((m.length >> 1) + 1) = m.length - (m.length >> 1) + 1
2097          // if odd:  (m.length + 1) - ((m.length >> 1) + 1) = m.length - (m.length >> 1)
2098          $temp = array_slice($temp[self::VALUE], ($m_length >> 1) + 1);
2099          // if even: (m.length - (m.length >> 1) + 1) + m.length = 2 * m.length - (m.length >> 1) + 1
2100          // if odd:  (m.length - (m.length >> 1)) + m.length     = 2 * m.length - (m.length >> 1)
2101          $temp = $this->_multiply($temp, false, $m, false);
2102  
2103          // at this point, if m had an odd number of digits, we'd be subtracting a 2 * m.length - (m.length >> 1) digit
2104          // number from a m.length + (m.length >> 1) + 1 digit number.  ie. there'd be an extra digit and the while loop
2105          // following this comment would loop a lot (hence our calling _regularBarrett() in that situation).
2106  
2107          $result = $this->_subtract($n[self::VALUE], false, $temp[self::VALUE], false);
2108  
2109          while ($this->_compare($result[self::VALUE], $result[self::SIGN], $m, false) >= 0) {
2110              $result = $this->_subtract($result[self::VALUE], $result[self::SIGN], $m, false);
2111          }
2112  
2113          return $result[self::VALUE];
2114      }
2115  
2116      /**
2117       * (Regular) Barrett Modular Reduction
2118       *
2119       * For numbers with more than four digits BigInteger::_barrett() is faster.  The difference between that and this
2120       * is that this function does not fold the denominator into a smaller form.
2121       *
2122       * @see self::_slidingWindow()
2123       * @access private
2124       * @param array $x
2125       * @param array $n
2126       * @return array
2127       */
2128      function _regularBarrett($x, $n)
2129      {
2130          static $cache = array(
2131              self::VARIABLE => array(),
2132              self::DATA => array()
2133          );
2134  
2135          $n_length = count($n);
2136  
2137          if (count($x) > 2 * $n_length) {
2138              $lhs = new static();
2139              $rhs = new static();
2140              $lhs->value = $x;
2141              $rhs->value = $n;
2142              list(, $temp) = $lhs->divide($rhs);
2143              return $temp->value;
2144          }
2145  
2146          if (($key = array_search($n, $cache[self::VARIABLE])) === false) {
2147              $key = count($cache[self::VARIABLE]);
2148              $cache[self::VARIABLE][] = $n;
2149              $lhs = new static();
2150              $lhs_value = &$lhs->value;
2151              $lhs_value = $this->_array_repeat(0, 2 * $n_length);
2152              $lhs_value[] = 1;
2153              $rhs = new static();
2154              $rhs->value = $n;
2155              list($temp, ) = $lhs->divide($rhs); // m.length
2156              $cache[self::DATA][] = $temp->value;
2157          }
2158  
2159          // 2 * m.length - (m.length - 1) = m.length + 1
2160          $temp = array_slice($x, $n_length - 1);
2161          // (m.length + 1) + m.length = 2 * m.length + 1
2162          $temp = $this->_multiply($temp, false, $cache[self::DATA][$key], false);
2163          // (2 * m.length + 1) - (m.length - 1) = m.length + 2
2164          $temp = array_slice($temp[self::VALUE], $n_length + 1);
2165  
2166          // m.length + 1
2167          $result = array_slice($x, 0, $n_length + 1);
2168          // m.length + 1
2169          $temp = $this->_multiplyLower($temp, false, $n, false, $n_length + 1);
2170          // $temp == array_slice($temp->_multiply($temp, false, $n, false)->value, 0, $n_length + 1)
2171  
2172          if ($this->_compare($result, false, $temp[self::VALUE], $temp[self::SIGN]) < 0) {
2173              $corrector_value = $this->_array_repeat(0, $n_length + 1);
2174              $corrector_value[count($corrector_value)] = 1;
2175              $result = $this->_add($result, false, $corrector_value, false);
2176              $result = $result[self::VALUE];
2177          }
2178  
2179          // at this point, we're subtracting a number with m.length + 1 digits from another number with m.length + 1 digits
2180          $result = $this->_subtract($result, false, $temp[self::VALUE], $temp[self::SIGN]);
2181          while ($this->_compare($result[self::VALUE], $result[self::SIGN], $n, false) > 0) {
2182              $result = $this->_subtract($result[self::VALUE], $result[self::SIGN], $n, false);
2183          }
2184  
2185          return $result[self::VALUE];
2186      }
2187  
2188      /**
2189       * Performs long multiplication up to $stop digits
2190       *
2191       * If you're going to be doing array_slice($product->value, 0, $stop), some cycles can be saved.
2192       *
2193       * @see self::_regularBarrett()
2194       * @param array $x_value
2195       * @param bool $x_negative
2196       * @param array $y_value
2197       * @param bool $y_negative
2198       * @param int $stop
2199       * @return array
2200       * @access private
2201       */
2202      function _multiplyLower($x_value, $x_negative, $y_value, $y_negative, $stop)
2203      {
2204          $x_length = count($x_value);
2205          $y_length = count($y_value);
2206  
2207          if (!$x_length || !$y_length) { // a 0 is being multiplied
2208              return array(
2209                  self::VALUE => array(),
2210                  self::SIGN => false
2211              );
2212          }
2213  
2214          if ($x_length < $y_length) {
2215              $temp = $x_value;
2216              $x_value = $y_value;
2217              $y_value = $temp;
2218  
2219              $x_length = count($x_value);
2220              $y_length = count($y_value);
2221          }
2222  
2223          $product_value = $this->_array_repeat(0, $x_length + $y_length);
2224  
2225          // the following for loop could be removed if the for loop following it
2226          // (the one with nested for loops) initially set $i to 0, but
2227          // doing so would also make the result in one set of unnecessary adds,
2228          // since on the outermost loops first pass, $product->value[$k] is going
2229          // to always be 0
2230  
2231          $carry = 0;
2232  
2233          for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0, $k = $i
2234              $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0
2235              $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
2236              $product_value[$j] = (int) ($temp - self::$baseFull * $carry);
2237          }
2238  
2239          if ($j < $stop) {
2240              $product_value[$j] = $carry;
2241          }
2242  
2243          // the above for loop is what the previous comment was talking about.  the
2244          // following for loop is the "one with nested for loops"
2245  
2246          for ($i = 1; $i < $y_length; ++$i) {
2247              $carry = 0;
2248  
2249              for ($j = 0, $k = $i; $j < $x_length && $k < $stop; ++$j, ++$k) {
2250                  $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry;
2251                  $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
2252                  $product_value[$k] = (int) ($temp - self::$baseFull * $carry);
2253              }
2254  
2255              if ($k < $stop) {
2256                  $product_value[$k] = $carry;
2257              }
2258          }
2259  
2260          return array(
2261              self::VALUE => $this->_trim($product_value),
2262              self::SIGN => $x_negative != $y_negative
2263          );
2264      }
2265  
2266      /**
2267       * Montgomery Modular Reduction
2268       *
2269       * ($x->_prepMontgomery($n))->_montgomery($n) yields $x % $n.
2270       * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=170 MPM 6.3} provides insights on how this can be
2271       * improved upon (basically, by using the comba method).  gcd($n, 2) must be equal to one for this function
2272       * to work correctly.
2273       *
2274       * @see self::_prepMontgomery()
2275       * @see self::_slidingWindow()
2276       * @access private
2277       * @param array $x
2278       * @param array $n
2279       * @return array
2280       */
2281      function _montgomery($x, $n)
2282      {
2283          static $cache = array(
2284              self::VARIABLE => array(),
2285              self::DATA => array()
2286          );
2287  
2288          if (($key = array_search($n, $cache[self::VARIABLE])) === false) {
2289              $key = count($cache[self::VARIABLE]);
2290              $cache[self::VARIABLE][] = $x;
2291              $cache[self::DATA][] = $this->_modInverse67108864($n);
2292          }
2293  
2294          $k = count($n);
2295  
2296          $result = array(self::VALUE => $x);
2297  
2298          for ($i = 0; $i < $k; ++$i) {
2299              $temp = $result[self::VALUE][$i] * $cache[self::DATA][$key];
2300              $temp = $temp - self::$baseFull * (self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31));
2301              $temp = $this->_regularMultiply(array($temp), $n);
2302              $temp = array_merge($this->_array_repeat(0, $i), $temp);
2303              $result = $this->_add($result[self::VALUE], false, $temp, false);
2304          }
2305  
2306          $result[self::VALUE] = array_slice($result[self::VALUE], $k);
2307  
2308          if ($this->_compare($result, false, $n, false) >= 0) {
2309              $result = $this->_subtract($result[self::VALUE], false, $n, false);
2310          }
2311  
2312          return $result[self::VALUE];
2313      }
2314  
2315      /**
2316       * Montgomery Multiply
2317       *
2318       * Interleaves the montgomery reduction and long multiplication algorithms together as described in
2319       * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=13 HAC 14.36}
2320       *
2321       * @see self::_prepMontgomery()
2322       * @see self::_montgomery()
2323       * @access private
2324       * @param array $x
2325       * @param array $y
2326       * @param array $m
2327       * @return array
2328       */
2329      function _montgomeryMultiply($x, $y, $m)
2330      {
2331          $temp = $this->_multiply($x, false, $y, false);
2332          return $this->_montgomery($temp[self::VALUE], $m);
2333  
2334          // the following code, although not callable, can be run independently of the above code
2335          // although the above code performed better in my benchmarks the following could might
2336          // perform better under different circumstances. in lieu of deleting it it's just been
2337          // made uncallable
2338  
2339          static $cache = array(
2340              self::VARIABLE => array(),
2341              self::DATA => array()
2342          );
2343  
2344          if (($key = array_search($m, $cache[self::VARIABLE])) === false) {
2345              $key = count($cache[self::VARIABLE]);
2346              $cache[self::VARIABLE][] = $m;
2347              $cache[self::DATA][] = $this->_modInverse67108864($m);
2348          }
2349  
2350          $n = max(count($x), count($y), count($m));
2351          $x = array_pad($x, $n, 0);
2352          $y = array_pad($y, $n, 0);
2353          $m = array_pad($m, $n, 0);
2354          $a = array(self::VALUE => $this->_array_repeat(0, $n + 1));
2355          for ($i = 0; $i < $n; ++$i) {
2356              $temp = $a[self::VALUE][0] + $x[$i] * $y[0];
2357              $temp = $temp - self::$baseFull * (self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31));
2358              $temp = $temp * $cache[self::DATA][$key];
2359              $temp = $temp - self::$baseFull * (self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31));
2360              $temp = $this->_add($this->_regularMultiply(array($x[$i]), $y), false, $this->_regularMultiply(array($temp), $m), false);
2361              $a = $this->_add($a[self::VALUE], false, $temp[self::VALUE], false);
2362              $a[self::VALUE] = array_slice($a[self::VALUE], 1);
2363          }
2364          if ($this->_compare($a[self::VALUE], false, $m, false) >= 0) {
2365              $a = $this->_subtract($a[self::VALUE], false, $m, false);
2366          }
2367          return $a[self::VALUE];
2368      }
2369  
2370      /**
2371       * Prepare a number for use in Montgomery Modular Reductions
2372       *
2373       * @see self::_montgomery()
2374       * @see self::_slidingWindow()
2375       * @access private
2376       * @param array $x
2377       * @param array $n
2378       * @return array
2379       */
2380      function _prepMontgomery($x, $n)
2381      {
2382          $lhs = new static();
2383          $lhs->value = array_merge($this->_array_repeat(0, count($n)), $x);
2384          $rhs = new static();
2385          $rhs->value = $n;
2386  
2387          list(, $temp) = $lhs->divide($rhs);
2388          return $temp->value;
2389      }
2390  
2391      /**
2392       * Modular Inverse of a number mod 2**26 (eg. 67108864)
2393       *
2394       * Based off of the bnpInvDigit function implemented and justified in the following URL:
2395       *
2396       * {@link http://www-cs-students.stanford.edu/~tjw/jsbn/jsbn.js}
2397       *
2398       * The following URL provides more info:
2399       *
2400       * {@link http://groups.google.com/group/sci.crypt/msg/7a137205c1be7d85}
2401       *
2402       * As for why we do all the bitmasking...  strange things can happen when converting from floats to ints. For
2403       * instance, on some computers, var_dump((int) -4294967297) yields int(-1) and on others, it yields
2404       * int(-2147483648).  To avoid problems stemming from this, we use bitmasks to guarantee that ints aren't
2405       * auto-converted to floats.  The outermost bitmask is present because without it, there's no guarantee that
2406       * the "residue" returned would be the so-called "common residue".  We use fmod, in the last step, because the
2407       * maximum possible $x is 26 bits and the maximum $result is 16 bits.  Thus, we have to be able to handle up to
2408       * 40 bits, which only 64-bit floating points will support.
2409       *
2410       * Thanks to Pedro Gimeno Fortea for input!
2411       *
2412       * @see self::_montgomery()
2413       * @access private
2414       * @param array $x
2415       * @return int
2416       */
2417      function _modInverse67108864($x) // 2**26 == 67,108,864
2418      {
2419          $x = -$x[0];
2420          $result = $x & 0x3; // x**-1 mod 2**2
2421          $result = ($result * (2 - $x * $result)) & 0xF; // x**-1 mod 2**4
2422          $result = ($result * (2 - ($x & 0xFF) * $result))  & 0xFF; // x**-1 mod 2**8
2423          $result = ($result * ((2 - ($x & 0xFFFF) * $result) & 0xFFFF)) & 0xFFFF; // x**-1 mod 2**16
2424          $result = fmod($result * (2 - fmod($x * $result, self::$baseFull)), self::$baseFull); // x**-1 mod 2**26
2425          return $result & self::$maxDigit;
2426      }
2427  
2428      /**
2429       * Calculates modular inverses.
2430       *
2431       * Say you have (30 mod 17 * x mod 17) mod 17 == 1.  x can be found using modular inverses.
2432       *
2433       * Here's an example:
2434       * <code>
2435       * <?php
2436       *    $a = new \phpseclib\Math\BigInteger(30);
2437       *    $b = new \phpseclib\Math\BigInteger(17);
2438       *
2439       *    $c = $a->modInverse($b);
2440       *    echo $c->toString(); // outputs 4
2441       *
2442       *    echo "\r\n";
2443       *
2444       *    $d = $a->multiply($c);
2445       *    list(, $d) = $d->divide($b);
2446       *    echo $d; // outputs 1 (as per the definition of modular inverse)
2447       * ?>
2448       * </code>
2449       *
2450       * @param \phpseclib\Math\BigInteger $n
2451       * @return \phpseclib\Math\BigInteger|false
2452       * @access public
2453       * @internal See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=21 HAC 14.64} for more information.
2454       */
2455      function modInverse($n)
2456      {
2457          switch (MATH_BIGINTEGER_MODE) {
2458              case self::MODE_GMP:
2459                  $temp = new static();
2460                  $temp->value = gmp_invert($this->value, $n->value);
2461  
2462                  return ($temp->value === false) ? false : $this->_normalize($temp);
2463          }
2464  
2465          static $zero, $one;
2466          if (!isset($zero)) {
2467              $zero = new static();
2468              $one = new static(1);
2469          }
2470  
2471          // $x mod -$n == $x mod $n.
2472          $n = $n->abs();
2473  
2474          if ($this->compare($zero) < 0) {
2475              $temp = $this->abs();
2476              $temp = $temp->modInverse($n);
2477              return $this->_normalize($n->subtract($temp));
2478          }
2479  
2480          extract($this->extendedGCD($n));
2481  
2482          if (!$gcd->equals($one)) {
2483              return false;
2484          }
2485  
2486          $x = $x->compare($zero) < 0 ? $x->add($n) : $x;
2487  
2488          return $this->compare($zero) < 0 ? $this->_normalize($n->subtract($x)) : $this->_normalize($x);
2489      }
2490  
2491      /**
2492       * Calculates the greatest common divisor and Bezout's identity.
2493       *
2494       * Say you have 693 and 609.  The GCD is 21.  Bezout's identity states that there exist integers x and y such that
2495       * 693*x + 609*y == 21.  In point of fact, there are actually an infinite number of x and y combinations and which
2496       * combination is returned is dependent upon which mode is in use.  See
2497       * {@link http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity Bezout's identity - Wikipedia} for more information.
2498       *
2499       * Here's an example:
2500       * <code>
2501       * <?php
2502       *    $a = new \phpseclib\Math\BigInteger(693);
2503       *    $b = new \phpseclib\Math\BigInteger(609);
2504       *
2505       *    extract($a->extendedGCD($b));
2506       *
2507       *    echo $gcd->toString() . "\r\n"; // outputs 21
2508       *    echo $a->toString() * $x->toString() + $b->toString() * $y->toString(); // outputs 21
2509       * ?>
2510       * </code>
2511       *
2512       * @param \phpseclib\Math\BigInteger $n
2513       * @return \phpseclib\Math\BigInteger
2514       * @access public
2515       * @internal Calculates the GCD using the binary xGCD algorithim described in
2516       *    {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=19 HAC 14.61}.  As the text above 14.61 notes,
2517       *    the more traditional algorithim requires "relatively costly multiple-precision divisions".
2518       */
2519      function extendedGCD($n)
2520      {
2521          switch (MATH_BIGINTEGER_MODE) {
2522              case self::MODE_GMP:
2523                  extract(gmp_gcdext($this->value, $n->value));
2524  
2525                  return array(
2526                      'gcd' => $this->_normalize(new static($g)),
2527                      'x'   => $this->_normalize(new static($s)),
2528                      'y'   => $this->_normalize(new static($t))
2529                  );
2530              case self::MODE_BCMATH:
2531                  // it might be faster to use the binary xGCD algorithim here, as well, but (1) that algorithim works
2532                  // best when the base is a power of 2 and (2) i don't think it'd make much difference, anyway.  as is,
2533                  // the basic extended euclidean algorithim is what we're using.
2534  
2535                  $u = $this->value;
2536                  $v = $n->value;
2537  
2538                  $a = '1';
2539                  $b = '0';
2540                  $c = '0';
2541                  $d = '1';
2542  
2543                  while (bccomp($v, '0', 0) != 0) {
2544                      $q = bcdiv($u, $v, 0);
2545  
2546                      $temp = $u;
2547                      $u = $v;
2548                      $v = bcsub($temp, bcmul($v, $q, 0), 0);
2549  
2550                      $temp = $a;
2551                      $a = $c;
2552                      $c = bcsub($temp, bcmul($a, $q, 0), 0);
2553  
2554                      $temp = $b;
2555                      $b = $d;
2556                      $d = bcsub($temp, bcmul($b, $q, 0), 0);
2557                  }
2558  
2559                  return array(
2560                      'gcd' => $this->_normalize(new static($u)),
2561                      'x'   => $this->_normalize(new static($a)),
2562                      'y'   => $this->_normalize(new static($b))
2563                  );
2564          }
2565  
2566          $y = $n->copy();
2567          $x = $this->copy();
2568          $g = new static();
2569          $g->value = array(1);
2570  
2571          while (!(($x->value[0] & 1)|| ($y->value[0] & 1))) {
2572              $x->_rshift(1);
2573              $y->_rshift(1);
2574              $g->_lshift(1);
2575          }
2576  
2577          $u = $x->copy();
2578          $v = $y->copy();
2579  
2580          $a = new static();
2581          $b = new static();
2582          $c = new static();
2583          $d = new static();
2584  
2585          $a->value = $d->value = $g->value = array(1);
2586          $b->value = $c->value = array();
2587  
2588          while (!empty($u->value)) {
2589              while (!($u->value[0] & 1)) {
2590                  $u->_rshift(1);
2591                  if ((!empty($a->value) && ($a->value[0] & 1)) || (!empty($b->value) && ($b->value[0] & 1))) {
2592                      $a = $a->add($y);
2593                      $b = $b->subtract($x);
2594                  }
2595                  $a->_rshift(1);
2596                  $b->_rshift(1);
2597              }
2598  
2599              while (!($v->value[0] & 1)) {
2600                  $v->_rshift(1);
2601                  if ((!empty($d->value) && ($d->value[0] & 1)) || (!empty($c->value) && ($c->value[0] & 1))) {
2602                      $c = $c->add($y);
2603                      $d = $d->subtract($x);
2604                  }
2605                  $c->_rshift(1);
2606                  $d->_rshift(1);
2607              }
2608  
2609              if ($u->compare($v) >= 0) {
2610                  $u = $u->subtract($v);
2611                  $a = $a->subtract($c);
2612                  $b = $b->subtract($d);
2613              } else {
2614                  $v = $v->subtract($u);
2615                  $c = $c->subtract($a);
2616                  $d = $d->subtract($b);
2617              }
2618          }
2619  
2620          return array(
2621              'gcd' => $this->_normalize($g->multiply($v)),
2622              'x'   => $this->_normalize($c),
2623              'y'   => $this->_normalize($d)
2624          );
2625      }
2626  
2627      /**
2628       * Calculates the greatest common divisor
2629       *
2630       * Say you have 693 and 609.  The GCD is 21.
2631       *
2632       * Here's an example:
2633       * <code>
2634       * <?php
2635       *    $a = new \phpseclib\Math\BigInteger(693);
2636       *    $b = new \phpseclib\Math\BigInteger(609);
2637       *
2638       *    $gcd = a->extendedGCD($b);
2639       *
2640       *    echo $gcd->toString() . "\r\n"; // outputs 21
2641       * ?>
2642       * </code>
2643       *
2644       * @param \phpseclib\Math\BigInteger $n
2645       * @return \phpseclib\Math\BigInteger
2646       * @access public
2647       */
2648      function gcd($n)
2649      {
2650          extract($this->extendedGCD($n));
2651          return $gcd;
2652      }
2653  
2654      /**
2655       * Absolute value.
2656       *
2657       * @return \phpseclib\Math\BigInteger
2658       * @access public
2659       */
2660      function abs()
2661      {
2662          $temp = new static();
2663  
2664          switch (MATH_BIGINTEGER_MODE) {
2665              case self::MODE_GMP:
2666                  $temp->value = gmp_abs($this->value);
2667                  break;
2668              case self::MODE_BCMATH:
2669                  $temp->value = (bccomp($this->value, '0', 0) < 0) ? substr($this->value, 1) : $this->value;
2670                  break;
2671              default:
2672                  $temp->value = $this->value;
2673          }
2674  
2675          return $temp;
2676      }
2677  
2678      /**
2679       * Compares two numbers.
2680       *
2681       * Although one might think !$x->compare($y) means $x != $y, it, in fact, means the opposite.  The reason for this is
2682       * demonstrated thusly:
2683       *
2684       * $x  > $y: $x->compare($y)  > 0
2685       * $x  < $y: $x->compare($y)  < 0
2686       * $x == $y: $x->compare($y) == 0
2687       *
2688       * Note how the same comparison operator is used.  If you want to test for equality, use $x->equals($y).
2689       *
2690       * @param \phpseclib\Math\BigInteger $y
2691       * @return int that is < 0 if $this is less than $y; > 0 if $this is greater than $y, and 0 if they are equal.
2692       * @access public
2693       * @see self::equals()
2694       * @internal Could return $this->subtract($x), but that's not as fast as what we do do.
2695       */
2696      function compare($y)
2697      {
2698          switch (MATH_BIGINTEGER_MODE) {
2699              case self::MODE_GMP:
2700                  $r = gmp_cmp($this->value, $y->value);
2701                  if ($r < -1) {
2702                      $r = -1;
2703                  }
2704                  if ($r > 1) {
2705                      $r = 1;
2706                  }
2707                  return $r;
2708              case self::MODE_BCMATH:
2709                  return bccomp($this->value, $y->value, 0);
2710          }
2711  
2712          return $this->_compare($this->value, $this->is_negative, $y->value, $y->is_negative);
2713      }
2714  
2715      /**
2716       * Compares two numbers.
2717       *
2718       * @param array $x_value
2719       * @param bool $x_negative
2720       * @param array $y_value
2721       * @param bool $y_negative
2722       * @return int
2723       * @see self::compare()
2724       * @access private
2725       */
2726      function _compare($x_value, $x_negative, $y_value, $y_negative)
2727      {
2728          if ($x_negative != $y_negative) {
2729              return (!$x_negative && $y_negative) ? 1 : -1;
2730          }
2731  
2732          $result = $x_negative ? -1 : 1;
2733  
2734          if (count($x_value) != count($y_value)) {
2735              return (count($x_value) > count($y_value)) ? $result : -$result;
2736          }
2737          $size = max(count($x_value), count($y_value));
2738  
2739          $x_value = array_pad($x_value, $size, 0);
2740          $y_value = array_pad($y_value, $size, 0);
2741  
2742          for ($i = count($x_value) - 1; $i >= 0; --$i) {
2743              if ($x_value[$i] != $y_value[$i]) {
2744                  return ($x_value[$i] > $y_value[$i]) ? $result : -$result;
2745              }
2746          }
2747  
2748          return 0;
2749      }
2750  
2751      /**
2752       * Tests the equality of two numbers.
2753       *
2754       * If you need to see if one number is greater than or less than another number, use BigInteger::compare()
2755       *
2756       * @param \phpseclib\Math\BigInteger $x
2757       * @return bool
2758       * @access public
2759       * @see self::compare()
2760       */
2761      function equals($x)
2762      {
2763          switch (MATH_BIGINTEGER_MODE) {
2764              case self::MODE_GMP:
2765                  return gmp_cmp($this->value, $x->value) == 0;
2766              default:
2767                  return $this->value === $x->value && $this->is_negative == $x->is_negative;
2768          }
2769      }
2770  
2771      /**
2772       * Set Precision
2773       *
2774       * Some bitwise operations give different results depending on the precision being used.  Examples include left
2775       * shift, not, and rotates.
2776       *
2777       * @param int $bits
2778       * @access public
2779       */
2780      function setPrecision($bits)
2781      {
2782          $this->precision = $bits;
2783          if (MATH_BIGINTEGER_MODE != self::MODE_BCMATH) {
2784              $this->bitmask = new static(chr((1 << ($bits & 0x7)) - 1) . str_repeat(chr(0xFF), $bits >> 3), 256);
2785          } else {
2786              $this->bitmask = new static(bcpow('2', $bits, 0));
2787          }
2788  
2789          $temp = $this->_normalize($this);
2790          $this->value = $temp->value;
2791      }
2792  
2793      /**
2794       * Logical And
2795       *
2796       * @param \phpseclib\Math\BigInteger $x
2797       * @access public
2798       * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
2799       * @return \phpseclib\Math\BigInteger
2800       */
2801      function bitwise_and($x)
2802      {
2803          switch (MATH_BIGINTEGER_MODE) {
2804              case self::MODE_GMP:
2805                  $temp = new static();
2806                  $temp->value = gmp_and($this->value, $x->value);
2807  
2808                  return $this->_normalize($temp);
2809              case self::MODE_BCMATH:
2810                  $left = $this->toBytes();
2811                  $right = $x->toBytes();
2812  
2813                  $length = max(strlen($left), strlen($right));
2814  
2815                  $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
2816                  $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
2817  
2818                  return $this->_normalize(new static($left & $right, 256));
2819          }
2820  
2821          $result = $this->copy();
2822  
2823          $length = min(count($x->value), count($this->value));
2824  
2825          $result->value = array_slice($result->value, 0, $length);
2826  
2827          for ($i = 0; $i < $length; ++$i) {
2828              $result->value[$i]&= $x->value[$i];
2829          }
2830  
2831          return $this->_normalize($result);
2832      }
2833  
2834      /**
2835       * Logical Or
2836       *
2837       * @param \phpseclib\Math\BigInteger $x
2838       * @access public
2839       * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
2840       * @return \phpseclib\Math\BigInteger
2841       */
2842      function bitwise_or($x)
2843      {
2844          switch (MATH_BIGINTEGER_MODE) {
2845              case self::MODE_GMP:
2846                  $temp = new static();
2847                  $temp->value = gmp_or($this->value, $x->value);
2848  
2849                  return $this->_normalize($temp);
2850              case self::MODE_BCMATH:
2851                  $left = $this->toBytes();
2852                  $right = $x->toBytes();
2853  
2854                  $length = max(strlen($left), strlen($right));
2855  
2856                  $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
2857                  $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
2858  
2859                  return $this->_normalize(new static($left | $right, 256));
2860          }
2861  
2862          $length = max(count($this->value), count($x->value));
2863          $result = $this->copy();
2864          $result->value = array_pad($result->value, $length, 0);
2865          $x->value = array_pad($x->value, $length, 0);
2866  
2867          for ($i = 0; $i < $length; ++$i) {
2868              $result->value[$i]|= $x->value[$i];
2869          }
2870  
2871          return $this->_normalize($result);
2872      }
2873  
2874      /**
2875       * Logical Exclusive-Or
2876       *
2877       * @param \phpseclib\Math\BigInteger $x
2878       * @access public
2879       * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
2880       * @return \phpseclib\Math\BigInteger
2881       */
2882      function bitwise_xor($x)
2883      {
2884          switch (MATH_BIGINTEGER_MODE) {
2885              case self::MODE_GMP:
2886                  $temp = new static();
2887                  $temp->value = gmp_xor(gmp_abs($this->value), gmp_abs($x->value));
2888                  return $this->_normalize($temp);
2889              case self::MODE_BCMATH:
2890                  $left = $this->toBytes();
2891                  $right = $x->toBytes();
2892  
2893                  $length = max(strlen($left), strlen($right));
2894  
2895                  $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
2896                  $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
2897  
2898                  return $this->_normalize(new static($left ^ $right, 256));
2899          }
2900  
2901          $length = max(count($this->value), count($x->value));
2902          $result = $this->copy();
2903          $result->is_negative = false;
2904          $result->value = array_pad($result->value, $length, 0);
2905          $x->value = array_pad($x->value, $length, 0);
2906  
2907          for ($i = 0; $i < $length; ++$i) {
2908              $result->value[$i]^= $x->value[$i];
2909          }
2910  
2911          return $this->_normalize($result);
2912      }
2913  
2914      /**
2915       * Logical Not
2916       *
2917       * @access public
2918       * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
2919       * @return \phpseclib\Math\BigInteger
2920       */
2921      function bitwise_not()
2922      {
2923          // calculuate "not" without regard to $this->precision
2924          // (will always result in a smaller number.  ie. ~1 isn't 1111 1110 - it's 0)
2925          $temp = $this->toBytes();
2926          if ($temp == '') {
2927              return $this->_normalize(new static());
2928          }
2929          $pre_msb = decbin(ord($temp[0]));
2930          $temp = ~$temp;
2931          $msb = decbin(ord($temp[0]));
2932          if (strlen($msb) == 8) {
2933              $msb = substr($msb, strpos($msb, '0'));
2934          }
2935          $temp[0] = chr(bindec($msb));
2936  
2937          // see if we need to add extra leading 1's
2938          $current_bits = strlen($pre_msb) + 8 * strlen($temp) - 8;
2939          $new_bits = $this->precision - $current_bits;
2940          if ($new_bits <= 0) {
2941              return $this->_normalize(new static($temp, 256));
2942          }
2943  
2944          // generate as many leading 1's as we need to.
2945          $leading_ones = chr((1 << ($new_bits & 0x7)) - 1) . str_repeat(chr(0xFF), $new_bits >> 3);
2946          $this->_base256_lshift($leading_ones, $current_bits);
2947  
2948          $temp = str_pad($temp, strlen($leading_ones), chr(0), STR_PAD_LEFT);
2949  
2950          return $this->_normalize(new static($leading_ones | $temp, 256));
2951      }
2952  
2953      /**
2954       * Logical Right Shift
2955       *
2956       * Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift.
2957       *
2958       * @param int $shift
2959       * @return \phpseclib\Math\BigInteger
2960       * @access public
2961       * @internal The only version that yields any speed increases is the internal version.
2962       */
2963      function bitwise_rightShift($shift)
2964      {
2965          $temp = new static();
2966  
2967          switch (MATH_BIGINTEGER_MODE) {
2968              case self::MODE_GMP:
2969                  static $two;
2970  
2971                  if (!isset($two)) {
2972                      $two = gmp_init('2');
2973                  }
2974  
2975                  $temp->value = gmp_div_q($this->value, gmp_pow($two, $shift));
2976  
2977                  break;
2978              case self::MODE_BCMATH:
2979                  $temp->value = bcdiv($this->value, bcpow('2', $shift, 0), 0);
2980  
2981                  break;
2982              default: // could just replace _lshift with this, but then all _lshift() calls would need to be rewritten
2983                       // and I don't want to do that...
2984                  $temp->value = $this->value;
2985                  $temp->_rshift($shift);
2986          }
2987  
2988          return $this->_normalize($temp);
2989      }
2990  
2991      /**
2992       * Logical Left Shift
2993       *
2994       * Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift.
2995       *
2996       * @param int $shift
2997       * @return \phpseclib\Math\BigInteger
2998       * @access public
2999       * @internal The only version that yields any speed increases is the internal version.
3000       */
3001      function bitwise_leftShift($shift)
3002      {
3003          $temp = new static();
3004  
3005          switch (MATH_BIGINTEGER_MODE) {
3006              case self::MODE_GMP:
3007                  static $two;
3008  
3009                  if (!isset($two)) {
3010                      $two = gmp_init('2');
3011                  }
3012  
3013                  $temp->value = gmp_mul($this->value, gmp_pow($two, $shift));
3014  
3015                  break;
3016              case self::MODE_BCMATH:
3017                  $temp->value = bcmul($this->value, bcpow('2', $shift, 0), 0);
3018  
3019                  break;
3020              default: // could just replace _rshift with this, but then all _lshift() calls would need to be rewritten
3021                       // and I don't want to do that...
3022                  $temp->value = $this->value;
3023                  $temp->_lshift($shift);
3024          }
3025  
3026          return $this->_normalize($temp);
3027      }
3028  
3029      /**
3030       * Logical Left Rotate
3031       *
3032       * Instead of the top x bits being dropped they're appended to the shifted bit string.
3033       *
3034       * @param int $shift
3035       * @return \phpseclib\Math\BigInteger
3036       * @access public
3037       */
3038      function bitwise_leftRotate($shift)
3039      {
3040          $bits = $this->toBytes();
3041  
3042          if ($this->precision > 0) {
3043              $precision = $this->precision;
3044              if (MATH_BIGINTEGER_MODE == self::MODE_BCMATH) {
3045                  $mask = $this->bitmask->subtract(new static(1));
3046                  $mask = $mask->toBytes();
3047              } else {
3048                  $mask = $this->bitmask->toBytes();
3049              }
3050          } else {
3051              $temp = ord($bits[0]);
3052              for ($i = 0; $temp >> $i; ++$i) {
3053              }
3054              $precision = 8 * strlen($bits) - 8 + $i;
3055              $mask = chr((1 << ($precision & 0x7)) - 1) . str_repeat(chr(0xFF), $precision >> 3);
3056          }
3057  
3058          if ($shift < 0) {
3059              $shift+= $precision;
3060          }
3061          $shift%= $precision;
3062  
3063          if (!$shift) {
3064              return $this->copy();
3065          }
3066  
3067          $left = $this->bitwise_leftShift($shift);
3068          $left = $left->bitwise_and(new static($mask, 256));
3069          $right = $this->bitwise_rightShift($precision - $shift);
3070          $result = MATH_BIGINTEGER_MODE != self::MODE_BCMATH ? $left->bitwise_or($right) : $left->add($right);
3071          return $this->_normalize($result);
3072      }
3073  
3074      /**
3075       * Logical Right Rotate
3076       *
3077       * Instead of the bottom x bits being dropped they're prepended to the shifted bit string.
3078       *
3079       * @param int $shift
3080       * @return \phpseclib\Math\BigInteger
3081       * @access public
3082       */
3083      function bitwise_rightRotate($shift)
3084      {
3085          return $this->bitwise_leftRotate(-$shift);
3086      }
3087  
3088      /**
3089       * Generates a random BigInteger
3090       *
3091       * Byte length is equal to $length. Uses \phpseclib\Crypt\Random if it's loaded and mt_rand if it's not.
3092       *
3093       * @param int $size
3094       * @return \phpseclib\Math\BigInteger
3095       * @access private
3096       */
3097      function _random_number_helper($size)
3098      {
3099          if (class_exists('\phpseclib\Crypt\Random')) {
3100              $random = Random::string($size);
3101          } else {
3102              $random = '';
3103  
3104              if ($size & 1) {
3105                  $random.= chr(mt_rand(0, 255));
3106              }
3107  
3108              $blocks = $size >> 1;
3109              for ($i = 0; $i < $blocks; ++$i) {
3110                  // mt_rand(-2147483648, 0x7FFFFFFF) always produces -2147483648 on some systems
3111                  $random.= pack('n', mt_rand(0, 0xFFFF));
3112              }
3113          }
3114  
3115          return new static($random, 256);
3116      }
3117  
3118      /**
3119       * Generate a random number
3120       *
3121       * Returns a random number between $min and $max where $min and $max
3122       * can be defined using one of the two methods:
3123       *
3124       * $min->random($max)
3125       * $max->random($min)
3126       *
3127       * @param \phpseclib\Math\BigInteger $arg1
3128       * @param \phpseclib\Math\BigInteger $arg2
3129       * @return \phpseclib\Math\BigInteger
3130       * @access public
3131       * @internal The API for creating random numbers used to be $a->random($min, $max), where $a was a BigInteger object.
3132       *           That method is still supported for BC purposes.
3133       */
3134      function random($arg1, $arg2 = false)
3135      {
3136          if ($arg1 === false) {
3137              return false;
3138          }
3139  
3140          if ($arg2 === false) {
3141              $max = $arg1;
3142              $min = $this;
3143          } else {
3144              $min = $arg1;
3145              $max = $arg2;
3146          }
3147  
3148          $compare = $max->compare($min);
3149  
3150          if (!$compare) {
3151              return $this->_normalize($min);
3152          } elseif ($compare < 0) {
3153              // if $min is bigger then $max, swap $min and $max
3154              $temp = $max;
3155              $max = $min;
3156              $min = $temp;
3157          }
3158  
3159          static $one;
3160          if (!isset($one)) {
3161              $one = new static(1);
3162          }
3163  
3164          $max = $max->subtract($min->subtract($one));
3165          $size = strlen(ltrim($max->toBytes(), chr(0)));
3166  
3167          /*
3168              doing $random % $max doesn't work because some numbers will be more likely to occur than others.
3169              eg. if $max is 140 and $random's max is 255 then that'd mean both $random = 5 and $random = 145
3170              would produce 5 whereas the only value of random that could produce 139 would be 139. ie.
3171              not all numbers would be equally likely. some would be more likely than others.
3172  
3173              creating a whole new random number until you find one that is within the range doesn't work
3174              because, for sufficiently small ranges, the likelihood that you'd get a number within that range
3175              would be pretty small. eg. with $random's max being 255 and if your $max being 1 the probability
3176              would be pretty high that $random would be greater than $max.
3177  
3178              phpseclib works around this using the technique described here:
3179  
3180              http://crypto.stackexchange.com/questions/5708/creating-a-small-number-from-a-cryptographically-secure-random-string
3181          */
3182          $random_max = new static(chr(1) . str_repeat("\0", $size), 256);
3183          $random = $this->_random_number_helper($size);
3184  
3185          list($max_multiple) = $random_max->divide($max);
3186          $max_multiple = $max_multiple->multiply($max);
3187  
3188          while ($random->compare($max_multiple) >= 0) {
3189              $random = $random->subtract($max_multiple);
3190              $random_max = $random_max->subtract($max_multiple);
3191              $random = $random->bitwise_leftShift(8);
3192              $random = $random->add($this->_random_number_helper(1));
3193              $random_max = $random_max->bitwise_leftShift(8);
3194              list($max_multiple) = $random_max->divide($max);
3195              $max_multiple = $max_multiple->multiply($max);
3196          }
3197          list(, $random) = $random->divide($max);
3198  
3199          return $this->_normalize($random->add($min));
3200      }
3201  
3202      /**
3203       * Generate a random prime number.
3204       *
3205       * If there's not a prime within the given range, false will be returned.
3206       * If more than $timeout seconds have elapsed, give up and return false.
3207       *
3208       * @param \phpseclib\Math\BigInteger $arg1
3209       * @param \phpseclib\Math\BigInteger $arg2
3210       * @param int $timeout
3211       * @return Math_BigInteger|false
3212       * @access public
3213       * @internal See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf#page=15 HAC 4.44}.
3214       */
3215      function randomPrime($arg1, $arg2 = false, $timeout = false)
3216      {
3217          if ($arg1 === false) {
3218              return false;
3219          }
3220  
3221          if ($arg2 === false) {
3222              $max = $arg1;
3223              $min = $this;
3224          } else {
3225              $min = $arg1;
3226              $max = $arg2;
3227          }
3228  
3229          $compare = $max->compare($min);
3230  
3231          if (!$compare) {
3232              return $min->isPrime() ? $min : false;
3233          } elseif ($compare < 0) {
3234              // if $min is bigger then $max, swap $min and $max
3235              $temp = $max;
3236              $max = $min;
3237              $min = $temp;
3238          }
3239  
3240          static $one, $two;
3241          if (!isset($one)) {
3242              $one = new static(1);
3243              $two = new static(2);
3244          }
3245  
3246          $start = time();
3247  
3248          $x = $this->random($min, $max);
3249  
3250          // gmp_nextprime() requires PHP 5 >= 5.2.0 per <http://php.net/gmp-nextprime>.
3251          if (MATH_BIGINTEGER_MODE == self::MODE_GMP && extension_loaded('gmp')) {
3252              $p = new static();
3253              $p->value = gmp_nextprime($x->value);
3254  
3255              if ($p->compare($max) <= 0) {
3256                  return $p;
3257              }
3258  
3259              if (!$min->equals($x)) {
3260                  $x = $x->subtract($one);
3261              }
3262  
3263              return $x->randomPrime($min, $x);
3264          }
3265  
3266          if ($x->equals($two)) {
3267              return $x;
3268          }
3269  
3270          $x->_make_odd();
3271          if ($x->compare($max) > 0) {
3272              // if $x > $max then $max is even and if $min == $max then no prime number exists between the specified range
3273              if ($min->equals($max)) {
3274                  return false;
3275              }
3276              $x = $min->copy();
3277              $x->_make_odd();
3278          }
3279  
3280          $initial_x = $x->copy();
3281  
3282          while (true) {
3283              if ($timeout !== false && time() - $start > $timeout) {
3284                  return false;
3285              }
3286  
3287              if ($x->isPrime()) {
3288                  return $x;
3289              }
3290  
3291              $x = $x->add($two);
3292  
3293              if ($x->compare($max) > 0) {
3294                  $x = $min->copy();
3295                  if ($x->equals($two)) {
3296                      return $x;
3297                  }
3298                  $x->_make_odd();
3299              }
3300  
3301              if ($x->equals($initial_x)) {
3302                  return false;
3303              }
3304          }
3305      }
3306  
3307      /**
3308       * Make the current number odd
3309       *
3310       * If the current number is odd it'll be unchanged.  If it's even, one will be added to it.
3311       *
3312       * @see self::randomPrime()
3313       * @access private
3314       */
3315      function _make_odd()
3316      {
3317          switch (MATH_BIGINTEGER_MODE) {
3318              case self::MODE_GMP:
3319                  gmp_setbit($this->value, 0);
3320                  break;
3321              case self::MODE_BCMATH:
3322                  if ($this->value[strlen($this->value) - 1] % 2 == 0) {
3323                      $this->value = bcadd($this->value, '1');
3324                  }
3325                  break;
3326              default:
3327                  $this->value[0] |= 1;
3328          }
3329      }
3330  
3331      /**
3332       * Checks a numer to see if it's prime
3333       *
3334       * Assuming the $t parameter is not set, this function has an error rate of 2**-80.  The main motivation for the
3335       * $t parameter is distributability.  BigInteger::randomPrime() can be distributed across multiple pageloads
3336       * on a website instead of just one.
3337       *
3338       * @param \phpseclib\Math\BigInteger $t
3339       * @return bool
3340       * @access public
3341       * @internal Uses the
3342       *     {@link http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test Miller-Rabin primality test}.  See
3343       *     {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf#page=8 HAC 4.24}.
3344       */
3345      function isPrime($t = false)
3346      {
3347          $length = strlen($this->toBytes());
3348  
3349          if (!$t) {
3350              // see HAC 4.49 "Note (controlling the error probability)"
3351              // @codingStandardsIgnoreStart
3352                   if ($length >= 163) { $t =  2; } // floor(1300 / 8)
3353              else if ($length >= 106) { $t =  3; } // floor( 850 / 8)
3354              else if ($length >= 81 ) { $t =  4; } // floor( 650 / 8)
3355              else if ($length >= 68 ) { $t =  5; } // floor( 550 / 8)
3356              else if ($length >= 56 ) { $t =  6; } // floor( 450 / 8)
3357              else if ($length >= 50 ) { $t =  7; } // floor( 400 / 8)
3358              else if ($length >= 43 ) { $t =  8; } // floor( 350 / 8)
3359              else if ($length >= 37 ) { $t =  9; } // floor( 300 / 8)
3360              else if ($length >= 31 ) { $t = 12; } // floor( 250 / 8)
3361              else if ($length >= 25 ) { $t = 15; } // floor( 200 / 8)
3362              else if ($length >= 18 ) { $t = 18; } // floor( 150 / 8)
3363              else                     { $t = 27; }
3364              // @codingStandardsIgnoreEnd
3365          }
3366  
3367          // ie. gmp_testbit($this, 0)
3368          // ie. isEven() or !isOdd()
3369          switch (MATH_BIGINTEGER_MODE) {
3370              case self::MODE_GMP:
3371                  return gmp_prob_prime($this->value, $t) != 0;
3372              case self::MODE_BCMATH:
3373                  if ($this->value === '2') {
3374                      return true;
3375                  }
3376                  if ($this->value[strlen($this->value) - 1] % 2 == 0) {
3377                      return false;
3378                  }
3379                  break;
3380              default:
3381                  if ($this->value == array(2)) {
3382                      return true;
3383                  }
3384                  if (~$this->value[0] & 1) {
3385                      return false;
3386                  }
3387          }
3388  
3389          static $primes, $zero, $one, $two;
3390  
3391          if (!isset($primes)) {
3392              $primes = array(
3393                  3,    5,    7,    11,   13,   17,   19,   23,   29,   31,   37,   41,   43,   47,   53,   59,
3394                  61,   67,   71,   73,   79,   83,   89,   97,   101,  103,  107,  109,  113,  127,  131,  137,
3395                  139,  149,  151,  157,  163,  167,  173,  179,  181,  191,  193,  197,  199,  211,  223,  227,
3396                  229,  233,  239,  241,  251,  257,  263,  269,  271,  277,  281,  283,  293,  307,  311,  313,
3397                  317,  331,  337,  347,  349,  353,  359,  367,  373,  379,  383,  389,  397,  401,  409,  419,
3398                  421,  431,  433,  439,  443,  449,  457,  461,  463,  467,  479,  487,  491,  499,  503,  509,
3399                  521,  523,  541,  547,  557,  563,  569,  571,  577,  587,  593,  599,  601,  607,  613,  617,
3400                  619,  631,  641,  643,  647,  653,  659,  661,  673,  677,  683,  691,  701,  709,  719,  727,
3401                  733,  739,  743,  751,  757,  761,  769,  773,  787,  797,  809,  811,  821,  823,  827,  829,
3402                  839,  853,  857,  859,  863,  877,  881,  883,  887,  907,  911,  919,  929,  937,  941,  947,
3403                  953,  967,  971,  977,  983,  991,  997
3404              );
3405  
3406              if (MATH_BIGINTEGER_MODE != self::MODE_INTERNAL) {
3407                  for ($i = 0; $i < count($primes); ++$i) {
3408                      $primes[$i] = new static($primes[$i]);
3409                  }
3410              }
3411  
3412              $zero = new static();
3413              $one = new static(1);
3414              $two = new static(2);
3415          }
3416  
3417          if ($this->equals($one)) {
3418              return false;
3419          }
3420  
3421          // see HAC 4.4.1 "Random search for probable primes"
3422          if (MATH_BIGINTEGER_MODE != self::MODE_INTERNAL) {
3423              foreach ($primes as $prime) {
3424                  list(, $r) = $this->divide($prime);
3425                  if ($r->equals($zero)) {
3426                      return $this->equals($prime);
3427                  }
3428              }
3429          } else {
3430              $value = $this->value;
3431              foreach ($primes as $prime) {
3432                  list(, $r) = $this->_divide_digit($value, $prime);
3433                  if (!$r) {
3434                      return count($value) == 1 && $value[0] == $prime;
3435                  }
3436              }
3437          }
3438  
3439          $n   = $this->copy();
3440          $n_1 = $n->subtract($one);
3441          $n_2 = $n->subtract($two);
3442  
3443          $r = $n_1->copy();
3444          $r_value = $r->value;
3445          // ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s));
3446          if (MATH_BIGINTEGER_MODE == self::MODE_BCMATH) {
3447              $s = 0;
3448              // if $n was 1, $r would be 0 and this would be an infinite loop, hence our $this->equals($one) check earlier
3449              while ($r->value[strlen($r->value) - 1] % 2 == 0) {
3450                  $r->value = bcdiv($r->value, '2', 0);
3451                  ++$s;
3452              }
3453          } else {
3454              for ($i = 0, $r_length = count($r_value); $i < $r_length; ++$i) {
3455                  $temp = ~$r_value[$i] & 0xFFFFFF;
3456                  for ($j = 1; ($temp >> $j) & 1; ++$j) {
3457                  }
3458                  if ($j != 25) {
3459                      break;
3460                  }
3461              }
3462              $s = 26 * $i + $j;
3463              $r->_rshift($s);
3464          }
3465  
3466          for ($i = 0; $i < $t; ++$i) {
3467              $a = $this->random($two, $n_2);
3468              $y = $a->modPow($r, $n);
3469  
3470              if (!$y->equals($one) && !$y->equals($n_1)) {
3471                  for ($j = 1; $j < $s && !$y->equals($n_1); ++$j) {
3472                      $y = $y->modPow($two, $n);
3473                      if ($y->equals($one)) {
3474                          return false;
3475                      }
3476                  }
3477  
3478                  if (!$y->equals($n_1)) {
3479                      return false;
3480                  }
3481              }
3482          }
3483          return true;
3484      }
3485  
3486      /**
3487       * Logical Left Shift
3488       *
3489       * Shifts BigInteger's by $shift bits.
3490       *
3491       * @param int $shift
3492       * @access private
3493       */
3494      function _lshift($shift)
3495      {
3496          if ($shift == 0) {
3497              return;
3498          }
3499  
3500          $num_digits = (int) ($shift / self::$base);
3501          $shift %= self::$base;
3502          $shift = 1 << $shift;
3503  
3504          $carry = 0;
3505  
3506          for ($i = 0; $i < count($this->value); ++$i) {
3507              $temp = $this->value[$i] * $shift + $carry;
3508              $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
3509              $this->value[$i] = (int) ($temp - $carry * self::$baseFull);
3510          }
3511  
3512          if ($carry) {
3513              $this->value[count($this->value)] = $carry;
3514          }
3515  
3516          while ($num_digits--) {
3517              array_unshift($this->value, 0);
3518          }
3519      }
3520  
3521      /**
3522       * Logical Right Shift
3523       *
3524       * Shifts BigInteger's by $shift bits.
3525       *
3526       * @param int $shift
3527       * @access private
3528       */
3529      function _rshift($shift)
3530      {
3531          if ($shift == 0) {
3532              return;
3533          }
3534  
3535          $num_digits = (int) ($shift / self::$base);
3536          $shift %= self::$base;
3537          $carry_shift = self::$base - $shift;
3538          $carry_mask = (1 << $shift) - 1;
3539  
3540          if ($num_digits) {
3541              $this->value = array_slice($this->value, $num_digits);
3542          }
3543  
3544          $carry = 0;
3545  
3546          for ($i = count($this->value) - 1; $i >= 0; --$i) {
3547              $temp = $this->value[$i] >> $shift | $carry;
3548              $carry = ($this->value[$i] & $carry_mask) << $carry_shift;
3549              $this->value[$i] = $temp;
3550          }
3551  
3552          $this->value = $this->_trim($this->value);
3553      }
3554  
3555      /**
3556       * Normalize
3557       *
3558       * Removes leading zeros and truncates (if necessary) to maintain the appropriate precision
3559       *
3560       * @param \phpseclib\Math\BigInteger $result
3561       * @return \phpseclib\Math\BigInteger
3562       * @see self::_trim()
3563       * @access private
3564       */
3565      function _normalize($result)
3566      {
3567          $result->precision = $this->precision;
3568          $result->bitmask = $this->bitmask;
3569  
3570          switch (MATH_BIGINTEGER_MODE) {
3571              case self::MODE_GMP:
3572                  if ($this->bitmask !== false) {
3573                      $flip = gmp_cmp($result->value, gmp_init(0)) < 0;
3574                      if ($flip) {
3575                          $result->value = gmp_neg($result->value);
3576                      }
3577                      $result->value = gmp_and($result->value, $result->bitmask->value);
3578                      if ($flip) {
3579                          $result->value = gmp_neg($result->value);
3580                      }
3581                  }
3582  
3583                  return $result;
3584              case self::MODE_BCMATH:
3585                  if (!empty($result->bitmask->value)) {
3586                      $result->value = bcmod($result->value, $result->bitmask->value);
3587                  }
3588  
3589                  return $result;
3590          }
3591  
3592          $value = &$result->value;
3593  
3594          if (!count($value)) {
3595              $result->is_negative = false;
3596              return $result;
3597          }
3598  
3599          $value = $this->_trim($value);
3600  
3601          if (!empty($result->bitmask->value)) {
3602              $length = min(count($value), count($this->bitmask->value));
3603              $value = array_slice($value, 0, $length);
3604  
3605              for ($i = 0; $i < $length; ++$i) {
3606                  $value[$i] = $value[$i] & $this->bitmask->value[$i];
3607              }
3608          }
3609  
3610          return $result;
3611      }
3612  
3613      /**
3614       * Trim
3615       *
3616       * Removes leading zeros
3617       *
3618       * @param array $value
3619       * @return \phpseclib\Math\BigInteger
3620       * @access private
3621       */
3622      function _trim($value)
3623      {
3624          for ($i = count($value) - 1; $i >= 0; --$i) {
3625              if ($value[$i]) {
3626                  break;
3627              }
3628              unset($value[$i]);
3629          }
3630  
3631          return $value;
3632      }
3633  
3634      /**
3635       * Array Repeat
3636       *
3637       * @param array $input
3638       * @param mixed $multiplier
3639       * @return array
3640       * @access private
3641       */
3642      function _array_repeat($input, $multiplier)
3643      {
3644          return ($multiplier) ? array_fill(0, $multiplier, $input) : array();
3645      }
3646  
3647      /**
3648       * Logical Left Shift
3649       *
3650       * Shifts binary strings $shift bits, essentially multiplying by 2**$shift.
3651       *
3652       * @param string $x (by reference)
3653       * @param int $shift
3654       * @return string
3655       * @access private
3656       */
3657      function _base256_lshift(&$x, $shift)
3658      {
3659          if ($shift == 0) {
3660              return;
3661          }
3662  
3663          $num_bytes = $shift >> 3; // eg. floor($shift/8)
3664          $shift &= 7; // eg. $shift % 8
3665  
3666          $carry = 0;
3667          for ($i = strlen($x) - 1; $i >= 0; --$i) {
3668              $temp = ord($x[$i]) << $shift | $carry;
3669              $x[$i] = chr($temp);
3670              $carry = $temp >> 8;
3671          }
3672          $carry = ($carry != 0) ? chr($carry) : '';
3673          $x = $carry . $x . str_repeat(chr(0), $num_bytes);
3674      }
3675  
3676      /**
3677       * Logical Right Shift
3678       *
3679       * Shifts binary strings $shift bits, essentially dividing by 2**$shift and returning the remainder.
3680       *
3681       * @param string $x (by referenc)
3682       * @param int $shift
3683       * @return string
3684       * @access private
3685       */
3686      function _base256_rshift(&$x, $shift)
3687      {
3688          if ($shift == 0) {
3689              $x = ltrim($x, chr(0));
3690              return '';
3691          }
3692  
3693          $num_bytes = $shift >> 3; // eg. floor($shift/8)
3694          $shift &= 7; // eg. $shift % 8
3695  
3696          $remainder = '';
3697          if ($num_bytes) {
3698              $start = $num_bytes > strlen($x) ? -strlen($x) : -$num_bytes;
3699              $remainder = substr($x, $start);
3700              $x = substr($x, 0, -$num_bytes);
3701          }
3702  
3703          $carry = 0;
3704          $carry_shift = 8 - $shift;
3705          for ($i = 0; $i < strlen($x); ++$i) {
3706              $temp = (ord($x[$i]) >> $shift) | $carry;
3707              $carry = (ord($x[$i]) << $carry_shift) & 0xFF;
3708              $x[$i] = chr($temp);
3709          }
3710          $x = ltrim($x, chr(0));
3711  
3712          $remainder = chr($carry >> $carry_shift) . $remainder;
3713  
3714          return ltrim($remainder, chr(0));
3715      }
3716  
3717      // one quirk about how the following functions are implemented is that PHP defines N to be an unsigned long
3718      // at 32-bits, while java's longs are 64-bits.
3719  
3720      /**
3721       * Converts 32-bit integers to bytes.
3722       *
3723       * @param int $x
3724       * @return string
3725       * @access private
3726       */
3727      function _int2bytes($x)
3728      {
3729          return ltrim(pack('N', $x), chr(0));
3730      }
3731  
3732      /**
3733       * Converts bytes to 32-bit integers
3734       *
3735       * @param string $x
3736       * @return int
3737       * @access private
3738       */
3739      function _bytes2int($x)
3740      {
3741          $temp = unpack('Nint', str_pad($x, 4, chr(0), STR_PAD_LEFT));
3742          return $temp['int'];
3743      }
3744  
3745      /**
3746       * DER-encode an integer
3747       *
3748       * The ability to DER-encode integers is needed to create RSA public keys for use with OpenSSL
3749       *
3750       * @see self::modPow()
3751       * @access private
3752       * @param int $length
3753       * @return string
3754       */
3755      function _encodeASN1Length($length)
3756      {
3757          if ($length <= 0x7F) {
3758              return chr($length);
3759          }
3760  
3761          $temp = ltrim(pack('N', $length), chr(0));
3762          return pack('Ca*', 0x80 | strlen($temp), $temp);
3763      }
3764  
3765      /**
3766       * Single digit division
3767       *
3768       * Even if int64 is being used the division operator will return a float64 value
3769       * if the dividend is not evenly divisible by the divisor. Since a float64 doesn't
3770       * have the precision of int64 this is a problem so, when int64 is being used,
3771       * we'll guarantee that the dividend is divisible by first subtracting the remainder.
3772       *
3773       * @access private
3774       * @param int $x
3775       * @param int $y
3776       * @return int
3777       */
3778      function _safe_divide($x, $y)
3779      {
3780          if (self::$base === 26) {
3781              return (int) (