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