library/phpsec/Math/BigInteger.php

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