securemail/vendor/phpseclib/phpseclib/phpseclib/Math/BigInteger.php

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