1<?php 2 3/** 4 * GMP BigInteger Engine 5 * 6 * PHP version 5 and 7 7 * 8 * @category Math 9 * @package BigInteger 10 * @author Jim Wigginton <terrafrost@php.net> 11 * @copyright 2017 Jim Wigginton 12 * @license http://www.opensource.org/licenses/mit-license.html MIT License 13 * @link http://pear.php.net/package/Math_BigInteger 14 */ 15 16namespace phpseclib3\Math\BigInteger\Engines; 17 18use phpseclib3\Exception\BadConfigurationException; 19 20/** 21 * GMP Engine. 22 * 23 * @package GMP 24 * @author Jim Wigginton <terrafrost@php.net> 25 * @access public 26 */ 27class GMP extends Engine 28{ 29 /** 30 * Can Bitwise operations be done fast? 31 * 32 * @see parent::bitwise_leftRotate() 33 * @see parent::bitwise_rightRotate() 34 * @access protected 35 */ 36 const FAST_BITWISE = true; 37 38 /** 39 * Engine Directory 40 * 41 * @see parent::setModExpEngine 42 * @access protected 43 */ 44 const ENGINE_DIR = 'GMP'; 45 46 /** 47 * Test for engine validity 48 * 49 * @return bool 50 * @see parent::__construct() 51 */ 52 public static function isValidEngine() 53 { 54 return extension_loaded('gmp'); 55 } 56 57 /** 58 * Default constructor 59 * 60 * @param mixed $x integer Base-10 number or base-$base number if $base set. 61 * @param int $base 62 * @see parent::__construct() 63 */ 64 public function __construct($x = 0, $base = 10) 65 { 66 if (!isset(static::$isValidEngine[static::class])) { 67 static::$isValidEngine[static::class] = self::isValidEngine(); 68 } 69 if (!static::$isValidEngine[static::class]) { 70 throw new BadConfigurationException('GMP is not setup correctly on this system'); 71 } 72 73 if ($x instanceof \GMP) { 74 $this->value = $x; 75 return; 76 } 77 78 $this->value = gmp_init(0); 79 80 parent::__construct($x, $base); 81 } 82 83 /** 84 * Initialize a GMP BigInteger Engine instance 85 * 86 * @param int $base 87 * @see parent::__construct() 88 */ 89 protected function initialize($base) 90 { 91 switch (abs($base)) { 92 case 256: 93 $this->value = gmp_import($this->value); 94 if ($this->is_negative) { 95 $this->value = -$this->value; 96 } 97 break; 98 case 16: 99 $temp = $this->is_negative ? '-0x' . $this->value : '0x' . $this->value; 100 $this->value = gmp_init($temp); 101 break; 102 case 10: 103 $this->value = gmp_init(isset($this->value) ? $this->value : '0'); 104 } 105 } 106 107 /** 108 * Converts a BigInteger to a base-10 number. 109 * 110 * @return string 111 */ 112 public function toString() 113 { 114 return (string)$this->value; 115 } 116 117 /** 118 * Converts a BigInteger to a bit string (eg. base-2). 119 * 120 * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're 121 * saved as two's compliment. 122 * 123 * @param bool $twos_compliment 124 * @return string 125 */ 126 public function toBits($twos_compliment = false) 127 { 128 $hex = $this->toHex($twos_compliment); 129 130 $bits = gmp_strval(gmp_init($hex, 16), 2); 131 132 if ($this->precision > 0) { 133 $bits = substr($bits, -$this->precision); 134 } 135 136 if ($twos_compliment && $this->compare(new static()) > 0 && $this->precision <= 0) { 137 return '0' . $bits; 138 } 139 140 return $bits; 141 } 142 143 /** 144 * Converts a BigInteger to a byte string (eg. base-256). 145 * 146 * @param bool $twos_compliment 147 * @return string 148 */ 149 public function toBytes($twos_compliment = false) 150 { 151 if ($twos_compliment) { 152 return $this->toBytesHelper(); 153 } 154 155 if (gmp_cmp($this->value, gmp_init(0)) == 0) { 156 return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : ''; 157 } 158 159 $temp = gmp_export($this->value); 160 161 return $this->precision > 0 ? 162 substr(str_pad($temp, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) : 163 ltrim($temp, chr(0)); 164 } 165 166 /** 167 * Adds two BigIntegers. 168 * 169 * @param GMP $y 170 * @return GMP 171 */ 172 public function add(GMP $y) 173 { 174 $temp = new self(); 175 $temp->value = $this->value + $y->value; 176 177 return $this->normalize($temp); 178 } 179 180 /** 181 * Subtracts two BigIntegers. 182 * 183 * @param GMP $y 184 * @return GMP 185 */ 186 public function subtract(GMP $y) 187 { 188 $temp = new self(); 189 $temp->value = $this->value - $y->value; 190 191 return $this->normalize($temp); 192 } 193 194 /** 195 * Multiplies two BigIntegers. 196 * 197 * @param GMP $x 198 * @return GMP 199 */ 200 public function multiply(GMP $x) 201 { 202 $temp = new self(); 203 $temp->value = $this->value * $x->value; 204 205 return $this->normalize($temp); 206 } 207 208 /** 209 * Divides two BigIntegers. 210 * 211 * Returns an array whose first element contains the quotient and whose second element contains the 212 * "common residue". If the remainder would be positive, the "common residue" and the remainder are the 213 * same. If the remainder would be negative, the "common residue" is equal to the sum of the remainder 214 * and the divisor (basically, the "common residue" is the first positive modulo). 215 * 216 * @param GMP $y 217 * @return array{GMP, GMP} 218 */ 219 public function divide(GMP $y) 220 { 221 $quotient = new self(); 222 $remainder = new self(); 223 224 list($quotient->value, $remainder->value) = gmp_div_qr($this->value, $y->value); 225 226 if (gmp_sign($remainder->value) < 0) { 227 $remainder->value = $remainder->value + gmp_abs($y->value); 228 } 229 230 return [$this->normalize($quotient), $this->normalize($remainder)]; 231 } 232 233 /** 234 * Compares two numbers. 235 * 236 * Although one might think !$x->compare($y) means $x != $y, it, in fact, means the opposite. The reason for this 237 * is demonstrated thusly: 238 * 239 * $x > $y: $x->compare($y) > 0 240 * $x < $y: $x->compare($y) < 0 241 * $x == $y: $x->compare($y) == 0 242 * 243 * Note how the same comparison operator is used. If you want to test for equality, use $x->equals($y). 244 * 245 * {@internal Could return $this->subtract($x), but that's not as fast as what we do do.} 246 * 247 * @param GMP $y 248 * @return int in case < 0 if $this is less than $y; > 0 if $this is greater than $y, and 0 if they are equal. 249 * @access public 250 * @see self::equals() 251 */ 252 public function compare(GMP $y) 253 { 254 $r = gmp_cmp($this->value, $y->value); 255 if ($r < -1) { 256 $r = -1; 257 } 258 if ($r > 1) { 259 $r = 1; 260 } 261 return $r; 262 } 263 264 /** 265 * Tests the equality of two numbers. 266 * 267 * If you need to see if one number is greater than or less than another number, use BigInteger::compare() 268 * 269 * @param GMP $x 270 * @return bool 271 */ 272 public function equals(GMP $x) 273 { 274 return $this->value == $x->value; 275 } 276 277 /** 278 * Calculates modular inverses. 279 * 280 * Say you have (30 mod 17 * x mod 17) mod 17 == 1. x can be found using modular inverses. 281 * 282 * @param GMP $n 283 * @return false|GMP 284 */ 285 public function modInverse(GMP $n) 286 { 287 $temp = new self(); 288 $temp->value = gmp_invert($this->value, $n->value); 289 290 return $temp->value === false ? false : $this->normalize($temp); 291 } 292 293 /** 294 * Calculates the greatest common divisor and Bezout's identity. 295 * 296 * Say you have 693 and 609. The GCD is 21. Bezout's identity states that there exist integers x and y such that 297 * 693*x + 609*y == 21. In point of fact, there are actually an infinite number of x and y combinations and which 298 * combination is returned is dependent upon which mode is in use. See 299 * {@link http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity Bezout's identity - Wikipedia} for more information. 300 * 301 * @param GMP $n 302 * @return GMP[] 303 */ 304 public function extendedGCD(GMP $n) 305 { 306 extract(gmp_gcdext($this->value, $n->value)); 307 308 return [ 309 'gcd' => $this->normalize(new self($g)), 310 'x' => $this->normalize(new self($s)), 311 'y' => $this->normalize(new self($t)) 312 ]; 313 } 314 315 /** 316 * Calculates the greatest common divisor 317 * 318 * Say you have 693 and 609. The GCD is 21. 319 * 320 * @param GMP $n 321 * @return GMP 322 */ 323 public function gcd(GMP $n) 324 { 325 $r = gmp_gcd($this->value, $n->value); 326 return $this->normalize(new self($r)); 327 } 328 329 /** 330 * Absolute value. 331 * 332 * @return GMP 333 * @access public 334 */ 335 public function abs() 336 { 337 $temp = new self(); 338 $temp->value = gmp_abs($this->value); 339 340 return $temp; 341 } 342 343 /** 344 * Logical And 345 * 346 * @param GMP $x 347 * @return GMP 348 */ 349 public function bitwise_and(GMP $x) 350 { 351 $temp = new self(); 352 $temp->value = $this->value & $x->value; 353 354 return $this->normalize($temp); 355 } 356 357 /** 358 * Logical Or 359 * 360 * @param GMP $x 361 * @return GMP 362 */ 363 public function bitwise_or(GMP $x) 364 { 365 $temp = new self(); 366 $temp->value = $this->value | $x->value; 367 368 return $this->normalize($temp); 369 } 370 371 /** 372 * Logical Exclusive Or 373 * 374 * @param GMP $x 375 * @return GMP 376 */ 377 public function bitwise_xor(GMP $x) 378 { 379 $temp = new self(); 380 $temp->value = $this->value ^ $x->value; 381 382 return $this->normalize($temp); 383 } 384 385 /** 386 * Logical Right Shift 387 * 388 * Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift. 389 * 390 * @param int $shift 391 * @return GMP 392 */ 393 public function bitwise_rightShift($shift) 394 { 395 // 0xFFFFFFFF >> 2 == -1 (on 32-bit systems) 396 // gmp_init('0xFFFFFFFF') >> 2 == gmp_init('0x3FFFFFFF') 397 398 $temp = new self(); 399 $temp->value = $this->value >> $shift; 400 401 return $this->normalize($temp); 402 } 403 404 /** 405 * Logical Left Shift 406 * 407 * Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift. 408 * 409 * @param int $shift 410 * @return GMP 411 */ 412 public function bitwise_leftShift($shift) 413 { 414 $temp = new self(); 415 $temp->value = $this->value << $shift; 416 417 return $this->normalize($temp); 418 } 419 420 /** 421 * Performs modular exponentiation. 422 * 423 * @param GMP $e 424 * @param GMP $n 425 * @return GMP 426 */ 427 public function modPow(GMP $e, GMP $n) 428 { 429 return $this->powModOuter($e, $n); 430 } 431 432 /** 433 * Performs modular exponentiation. 434 * 435 * Alias for modPow(). 436 * 437 * @param GMP $e 438 * @param GMP $n 439 * @return GMP 440 */ 441 public function powMod(GMP $e, GMP $n) 442 { 443 return $this->powModOuter($e, $n); 444 } 445 446 /** 447 * Performs modular exponentiation. 448 * 449 * @param GMP $e 450 * @param GMP $n 451 * @return GMP 452 */ 453 protected function powModInner(GMP $e, GMP $n) 454 { 455 $class = static::$modexpEngine[static::class]; 456 return $class::powModHelper($this, $e, $n); 457 } 458 459 /** 460 * Normalize 461 * 462 * Removes leading zeros and truncates (if necessary) to maintain the appropriate precision 463 * 464 * @param GMP $result 465 * @return GMP 466 */ 467 protected function normalize(GMP $result) 468 { 469 $result->precision = $this->precision; 470 $result->bitmask = $this->bitmask; 471 472 if ($result->bitmask !== false) { 473 $flip = $result->value < 0; 474 if ($flip) { 475 $result->value = -$result->value; 476 } 477 $result->value = $result->value & $result->bitmask->value; 478 if ($flip) { 479 $result->value = -$result->value; 480 } 481 } 482 483 return $result; 484 } 485 486 /** 487 * Performs some post-processing for randomRangePrime 488 * 489 * @param Engine $x 490 * @param Engine $min 491 * @param Engine $max 492 * @return GMP 493 */ 494 protected static function randomRangePrimeInner(Engine $x, Engine $min, Engine $max) 495 { 496 $p = gmp_nextprime($x->value); 497 498 if ($p <= $max->value) { 499 return new self($p); 500 } 501 502 if ($min->value != $x->value) { 503 $x = new self($x->value - 1); 504 } 505 506 return self::randomRangePrime($min, $x); 507 } 508 509 /** 510 * Generate a random prime number between a range 511 * 512 * If there's not a prime within the given range, false will be returned. 513 * 514 * @param GMP $min 515 * @param GMP $max 516 * @return false|GMP 517 */ 518 public static function randomRangePrime(GMP $min, GMP $max) 519 { 520 return self::randomRangePrimeOuter($min, $max); 521 } 522 523 /** 524 * Generate a random number between a range 525 * 526 * Returns a random number between $min and $max where $min and $max 527 * can be defined using one of the two methods: 528 * 529 * BigInteger::randomRange($min, $max) 530 * BigInteger::randomRange($max, $min) 531 * 532 * @param GMP $min 533 * @param GMP $max 534 * @return GMP 535 */ 536 public static function randomRange(GMP $min, GMP $max) 537 { 538 return self::randomRangeHelper($min, $max); 539 } 540 541 /** 542 * Make the current number odd 543 * 544 * If the current number is odd it'll be unchanged. If it's even, one will be added to it. 545 * 546 * @see self::randomPrime() 547 */ 548 protected function make_odd() 549 { 550 gmp_setbit($this->value, 0); 551 } 552 553 /** 554 * Tests Primality 555 * 556 * @param int $t 557 * @return bool 558 */ 559 protected function testPrimality($t) 560 { 561 return gmp_prob_prime($this->value, $t) != 0; 562 } 563 564 /** 565 * Calculates the nth root of a biginteger. 566 * 567 * Returns the nth root of a positive biginteger, where n defaults to 2 568 * 569 * @param int $n 570 * @return GMP 571 */ 572 protected function rootInner($n) 573 { 574 $root = new self(); 575 $root->value = gmp_root($this->value, $n); 576 return $this->normalize($root); 577 } 578 579 /** 580 * Performs exponentiation. 581 * 582 * @param GMP $n 583 * @return GMP 584 */ 585 public function pow(GMP $n) 586 { 587 $temp = new self(); 588 $temp->value = $this->value ** $n->value; 589 590 return $this->normalize($temp); 591 } 592 593 /** 594 * Return the minimum BigInteger between an arbitrary number of BigIntegers. 595 * 596 * @param GMP ...$nums 597 * @return GMP 598 */ 599 public static function min(GMP ...$nums) 600 { 601 return self::minHelper($nums); 602 } 603 604 /** 605 * Return the maximum BigInteger between an arbitrary number of BigIntegers. 606 * 607 * @param GMP ...$nums 608 * @return GMP 609 */ 610 public static function max(GMP ...$nums) 611 { 612 return self::maxHelper($nums); 613 } 614 615 /** 616 * Tests BigInteger to see if it is between two integers, inclusive 617 * 618 * @param GMP $min 619 * @param GMP $max 620 * @return bool 621 */ 622 public function between(GMP $min, GMP $max) 623 { 624 return $this->compare($min) >= 0 && $this->compare($max) <= 0; 625 } 626 627 /** 628 * Create Recurring Modulo Function 629 * 630 * Sometimes it may be desirable to do repeated modulos with the same number outside of 631 * modular exponentiation 632 * 633 * @return callable 634 */ 635 public function createRecurringModuloFunction() 636 { 637 $temp = $this->value; 638 return function (GMP $x) use ($temp) { 639 return new GMP($x->value % $temp); 640 }; 641 } 642 643 /** 644 * Scan for 1 and right shift by that amount 645 * 646 * ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s)); 647 * 648 * @param GMP $r 649 * @return int 650 */ 651 public static function scan1divide(GMP $r) 652 { 653 $s = gmp_scan1($r->value, 0); 654 $r->value >>= $s; 655 return $s; 656 } 657 658 /** 659 * Is Odd? 660 * 661 * @return bool 662 */ 663 public function isOdd() 664 { 665 return gmp_testbit($this->value, 0); 666 } 667 668 /** 669 * Tests if a bit is set 670 * 671 * @return bool 672 */ 673 public function testBit($x) 674 { 675 return gmp_testbit($this->value, $x); 676 } 677 678 /** 679 * Is Negative? 680 * 681 * @return bool 682 */ 683 public function isNegative() 684 { 685 return gmp_sign($this->value) == -1; 686 } 687 688 /** 689 * Negate 690 * 691 * Given $k, returns -$k 692 * 693 * @return GMP 694 */ 695 public function negate() 696 { 697 $temp = clone $this; 698 $temp->value = -$this->value; 699 700 return $temp; 701 } 702} 703