1<?php 2 3/** 4 * Pure-PHP 64-bit 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 ParagonIE\ConstantTime\Hex; 19 20/** 21 * Pure-PHP 64-bit Engine. 22 * 23 * Uses 64-bit integers if int size is 8 bits 24 * 25 * @package PHP 26 * @author Jim Wigginton <terrafrost@php.net> 27 * @access public 28 */ 29class PHP64 extends PHP 30{ 31 // Constants used by PHP.php 32 const BASE = 31; 33 const BASE_FULL = 0x80000000; 34 const MAX_DIGIT = 0x7FFFFFFF; 35 const MSB = 0x40000000; 36 37 /** 38 * MAX10 in greatest MAX10LEN satisfying 39 * MAX10 = 10**MAX10LEN <= 2**BASE. 40 */ 41 const MAX10 = 1000000000; 42 43 /** 44 * MAX10LEN in greatest MAX10LEN satisfying 45 * MAX10 = 10**MAX10LEN <= 2**BASE. 46 */ 47 const MAX10LEN = 9; 48 const MAX_DIGIT2 = 4611686018427387904; 49 /**#@-*/ 50 51 /** 52 * Modular Exponentiation Engine 53 * 54 * @var string 55 */ 56 protected static $modexpEngine; 57 58 /** 59 * Engine Validity Flag 60 * 61 * @var bool 62 */ 63 protected static $isValidEngine; 64 65 /** 66 * Primes > 2 and < 1000 67 * 68 * @var array 69 */ 70 protected static $primes; 71 72 /** 73 * BigInteger(0) 74 * 75 * @var \phpseclib3\Math\BigInteger\Engines\PHP64 76 */ 77 protected static $zero; 78 79 /** 80 * BigInteger(1) 81 * 82 * @var \phpseclib3\Math\BigInteger\Engines\PHP64 83 */ 84 protected static $one; 85 86 /** 87 * BigInteger(2) 88 * 89 * @var \phpseclib3\Math\BigInteger\Engines\PHP64 90 */ 91 protected static $two; 92 93 /** 94 * Initialize a PHP64 BigInteger Engine instance 95 * 96 * @param int $base 97 * @see parent::initialize() 98 */ 99 protected function initialize($base) 100 { 101 if ($base != 256 && $base != -256) { 102 return parent::initialize($base); 103 } 104 105 $val = $this->value; 106 $this->value = []; 107 $vals = &$this->value; 108 $i = strlen($val); 109 if (!$i) { 110 return; 111 } 112 113 while (true) { 114 $i-= 4; 115 if ($i < 0) { 116 if ($i == -4) { 117 break; 118 } 119 $val = substr($val, 0, 4 + $i); 120 $val = str_pad($val, 4, "\0", STR_PAD_LEFT); 121 if ($val == "\0\0\0\0") { 122 break; 123 } 124 $i = 0; 125 } 126 list(, $digit) = unpack('N', substr($val, $i, 4)); 127 $step = count($vals) & 7; 128 if (!$step) { 129 $digit&= static::MAX_DIGIT; 130 $i++; 131 } else { 132 $shift = 8 - $step; 133 $digit>>= $shift; 134 $shift = 32 - $shift; 135 $digit&= (1 << $shift) - 1; 136 $temp = $i > 0 ? ord($val[$i - 1]) : 0; 137 $digit|= ($temp << $shift) & 0x7F000000; 138 } 139 $vals[] = $digit; 140 } 141 while (end($vals) === 0) { 142 array_pop($vals); 143 } 144 reset($vals); 145 } 146 147 /** 148 * Test for engine validity 149 * 150 * @see parent::__construct() 151 * @return bool 152 */ 153 public static function isValidEngine() 154 { 155 return PHP_INT_SIZE >= 8; 156 } 157 158 /** 159 * Adds two BigIntegers. 160 * 161 * @param PHP64 $y 162 * @return PHP64 163 */ 164 public function add(PHP64 $y) 165 { 166 $temp = self::addHelper($this->value, $this->is_negative, $y->value, $y->is_negative); 167 168 return $this->convertToObj($temp); 169 } 170 171 /** 172 * Subtracts two BigIntegers. 173 * 174 * @param PHP64 $y 175 * @return PHP64 176 */ 177 public function subtract(PHP64 $y) 178 { 179 $temp = self::subtractHelper($this->value, $this->is_negative, $y->value, $y->is_negative); 180 181 return $this->convertToObj($temp); 182 } 183 184 /** 185 * Multiplies two BigIntegers. 186 * 187 * @param PHP64 $y 188 * @return PHP64 189 */ 190 public function multiply(PHP64 $y) 191 { 192 $temp = self::multiplyHelper($this->value, $this->is_negative, $y->value, $y->is_negative); 193 194 return $this->convertToObj($temp); 195 } 196 197 /** 198 * Divides two BigIntegers. 199 * 200 * Returns an array whose first element contains the quotient and whose second element contains the 201 * "common residue". If the remainder would be positive, the "common residue" and the remainder are the 202 * same. If the remainder would be negative, the "common residue" is equal to the sum of the remainder 203 * and the divisor (basically, the "common residue" is the first positive modulo). 204 * 205 * @param PHP64 $y 206 * @return PHP64 207 */ 208 public function divide(PHP64 $y) 209 { 210 return $this->divideHelper($y); 211 } 212 213 /** 214 * Calculates modular inverses. 215 * 216 * Say you have (30 mod 17 * x mod 17) mod 17 == 1. x can be found using modular inverses. 217 * @param PHP64 $n 218 * @return false|PHP64 219 */ 220 public function modInverse(PHP64 $n) 221 { 222 return $this->modInverseHelper($n); 223 } 224 225 /** 226 * Calculates modular inverses. 227 * 228 * Say you have (30 mod 17 * x mod 17) mod 17 == 1. x can be found using modular inverses. 229 * @param PHP64 $n 230 * @return PHP64[] 231 */ 232 public function extendedGCD(PHP64 $n) 233 { 234 return $this->extendedGCDHelper($n); 235 } 236 237 /** 238 * Calculates the greatest common divisor 239 * 240 * Say you have 693 and 609. The GCD is 21. 241 * 242 * @param PHP64 $n 243 * @return PHP64 244 */ 245 public function gcd(PHP64 $n) 246 { 247 return $this->extendedGCD($n)['gcd']; 248 } 249 250 /** 251 * Logical And 252 * 253 * @param PHP64 $x 254 * @return PHP64 255 */ 256 public function bitwise_and(PHP64 $x) 257 { 258 return $this->bitwiseAndHelper($x); 259 } 260 261 /** 262 * Logical Or 263 * 264 * @param PHP64 $x 265 * @return PHP64 266 */ 267 public function bitwise_or(PHP64 $x) 268 { 269 return $this->bitwiseOrHelper($x); 270 } 271 272 /** 273 * Logical Exclusive Or 274 * 275 * @param PHP64 $x 276 * @return PHP64 277 */ 278 public function bitwise_xor(PHP64 $x) 279 { 280 return $this->bitwiseXorHelper($x); 281 } 282 283 /** 284 * Compares two numbers. 285 * 286 * Although one might think !$x->compare($y) means $x != $y, it, in fact, means the opposite. The reason for this is 287 * demonstrated thusly: 288 * 289 * $x > $y: $x->compare($y) > 0 290 * $x < $y: $x->compare($y) < 0 291 * $x == $y: $x->compare($y) == 0 292 * 293 * Note how the same comparison operator is used. If you want to test for equality, use $x->equals($y). 294 * 295 * {@internal Could return $this->subtract($x), but that's not as fast as what we do do.} 296 * 297 * @param PHP64 $y 298 * @return int in case < 0 if $this is less than $y; > 0 if $this is greater than $y, and 0 if they are equal. 299 * @access public 300 * @see self::equals() 301 */ 302 public function compare(PHP64 $y) 303 { 304 return parent::compareHelper($this->value, $this->is_negative, $y->value, $y->is_negative); 305 } 306 307 /** 308 * Tests the equality of two numbers. 309 * 310 * If you need to see if one number is greater than or less than another number, use BigInteger::compare() 311 * 312 * @param PHP64 $x 313 * @return bool 314 */ 315 public function equals(PHP64 $x) 316 { 317 return $this->value === $x->value && $this->is_negative == $x->is_negative; 318 } 319 320 /** 321 * Performs modular exponentiation. 322 * 323 * @param PHP64 $e 324 * @param PHP64 $n 325 * @return PHP64 326 */ 327 public function modPow(PHP64 $e, PHP64 $n) 328 { 329 return $this->powModOuter($e, $n); 330 } 331 332 /** 333 * Performs modular exponentiation. 334 * 335 * Alias for modPow(). 336 * 337 * @param PHP64 $e 338 * @param PHP64 $n 339 * @return PHP64 340 */ 341 public function powMod(PHP64 $e, PHP64 $n) 342 { 343 return $this->powModOuter($e, $n); 344 } 345 346 /** 347 * Generate a random prime number between a range 348 * 349 * If there's not a prime within the given range, false will be returned. 350 * 351 * @param PHP64 $min 352 * @param PHP64 $max 353 * @return false|PHP64 354 */ 355 public static function randomRangePrime(PHP64 $min, PHP64 $max) 356 { 357 return self::randomRangePrimeOuter($min, $max); 358 } 359 360 /** 361 * Generate a random number between a range 362 * 363 * Returns a random number between $min and $max where $min and $max 364 * can be defined using one of the two methods: 365 * 366 * BigInteger::randomRange($min, $max) 367 * BigInteger::randomRange($max, $min) 368 * 369 * @param PHP64 $min 370 * @param PHP64 $max 371 * @return PHP64 372 */ 373 public static function randomRange(PHP64 $min, PHP64 $max) 374 { 375 return self::randomRangeHelper($min, $max); 376 } 377 378 /** 379 * Performs exponentiation. 380 * 381 * @param PHP64 $n 382 * @return PHP64 383 */ 384 public function pow(PHP64 $n) 385 { 386 return $this->powHelper($n); 387 } 388 389 /** 390 * Return the minimum BigInteger between an arbitrary number of BigIntegers. 391 * 392 * @param PHP64 ...$nums 393 * @return PHP64 394 */ 395 public static function min(PHP64 ...$nums) 396 { 397 return self::minHelper($nums); 398 } 399 400 /** 401 * Return the maximum BigInteger between an arbitrary number of BigIntegers. 402 * 403 * @param PHP64 ...$nums 404 * @return PHP64 405 */ 406 public static function max(PHP64 ...$nums) 407 { 408 return self::maxHelper($nums); 409 } 410 411 /** 412 * Tests BigInteger to see if it is between two integers, inclusive 413 * 414 * @param PHP64 $min 415 * @param PHP64 $max 416 * @return bool 417 */ 418 public function between(PHP64 $min, PHP64 $max) 419 { 420 return $this->compare($min) >= 0 && $this->compare($max) <= 0; 421 } 422}