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