plugins/OStatus/extlib/phpseclib/Math/BigInteger.php

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