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