ILIAS  release_5-4 Revision v5.4.26-12-gabc799a52e6
phpseclib\Math\BigInteger Class Reference
+ Collaboration diagram for phpseclib\Math\BigInteger:

Public Member Functions

 __construct ($x=0, $base=10)
 Converts base-2, base-10, base-16, and binary strings (base-256) to BigIntegers. More...
 
 toBytes ($twos_compliment=false)
 Converts a BigInteger to a byte string (eg. More...
 
 toHex ($twos_compliment=false)
 Converts a BigInteger to a hex string (eg. More...
 
 toBits ($twos_compliment=false)
 Converts a BigInteger to a bit string (eg. More...
 
 toString ()
 Converts a BigInteger to a base-10 number. More...
 
 copy ()
 Copy an object. More...
 
 __toString ()
 __toString() magic method More...
 
 __clone ()
 __clone() magic method More...
 
 __sleep ()
 __sleep() magic method More...
 
 __wakeup ()
 __wakeup() magic method More...
 
 __debugInfo ()
 __debugInfo() magic method More...
 
 add ($y)
 Adds two BigIntegers. More...
 
 _add ($x_value, $x_negative, $y_value, $y_negative)
 Performs addition. More...
 
 subtract ($y)
 Subtracts two BigIntegers. More...
 
 _subtract ($x_value, $x_negative, $y_value, $y_negative)
 Performs subtraction. More...
 
 multiply ($x)
 Multiplies two BigIntegers. More...
 
 _multiply ($x_value, $x_negative, $y_value, $y_negative)
 Performs multiplication. More...
 
 _regularMultiply ($x_value, $y_value)
 Performs long multiplication on two BigIntegers. More...
 
 _karatsuba ($x_value, $y_value)
 Performs Karatsuba multiplication on two BigIntegers. More...
 
 _square ($x=false)
 Performs squaring. More...
 
 _baseSquare ($value)
 Performs traditional squaring on two BigIntegers. More...
 
 _karatsubaSquare ($value)
 Performs Karatsuba "squaring" on two BigIntegers. More...
 
 divide ($y)
 Divides two BigIntegers. More...
 
 _divide_digit ($dividend, $divisor)
 Divides a BigInteger by a regular integer. More...
 
 modPow ($e, $n)
 Performs modular exponentiation. More...
 
 powMod ($e, $n)
 Performs modular exponentiation. More...
 
 _slidingWindow ($e, $n, $mode)
 Sliding Window k-ary Modular Exponentiation. More...
 
 _reduce ($x, $n, $mode)
 Modular reduction. More...
 
 _prepareReduce ($x, $n, $mode)
 Modular reduction preperation. More...
 
 _multiplyReduce ($x, $y, $n, $mode)
 Modular multiply. More...
 
 _squareReduce ($x, $n, $mode)
 Modular square. More...
 
 _mod2 ($n)
 Modulos for Powers of Two. More...
 
 _barrett ($n, $m)
 Barrett Modular Reduction. More...
 
 _regularBarrett ($x, $n)
 (Regular) Barrett Modular Reduction More...
 
 _multiplyLower ($x_value, $x_negative, $y_value, $y_negative, $stop)
 Performs long multiplication up to $stop digits. More...
 
 _montgomery ($x, $n)
 Montgomery Modular Reduction. More...
 
 _montgomeryMultiply ($x, $y, $m)
 Montgomery Multiply. More...
 
 _prepMontgomery ($x, $n)
 Prepare a number for use in Montgomery Modular Reductions. More...
 
 _modInverse67108864 ($x)
 Modular Inverse of a number mod 2**26 (eg. More...
 
 modInverse ($n)
 Calculates modular inverses. More...
 
 extendedGCD ($n)
 Calculates the greatest common divisor and Bezout's identity. More...
 
 gcd ($n)
 Calculates the greatest common divisor. More...
 
 abs ()
 Absolute value. More...
 
 compare ($y)
 Compares two numbers. More...
 
 _compare ($x_value, $x_negative, $y_value, $y_negative)
 Compares two numbers. More...
 
 equals ($x)
 Tests the equality of two numbers. More...
 
 setPrecision ($bits)
 Set Precision. More...
 
 bitwise_and ($x)
 Logical And. More...
 
 bitwise_or ($x)
 Logical Or. More...
 
 bitwise_xor ($x)
 Logical Exclusive-Or. More...
 
 bitwise_not ()
 Logical Not. More...
 
 bitwise_rightShift ($shift)
 Logical Right Shift. More...
 
 bitwise_leftShift ($shift)
 Logical Left Shift. More...
 
 bitwise_leftRotate ($shift)
 Logical Left Rotate. More...
 
 bitwise_rightRotate ($shift)
 Logical Right Rotate. More...
 
 _random_number_helper ($size)
 Generates a random BigInteger. More...
 
 random ($arg1, $arg2=false)
 Generate a random number. More...
 
 randomPrime ($arg1, $arg2=false, $timeout=false)
 Generate a random prime number. More...
 
 _make_odd ()
 Make the current number odd. More...
 
 isPrime ($t=false)
 Checks a numer to see if it's prime. More...
 
 _lshift ($shift)
 Logical Left Shift. More...
 
 _rshift ($shift)
 Logical Right Shift. More...
 
 _normalize ($result)
 Normalize. More...
 
 _trim ($value)
 Trim. More...
 
 _array_repeat ($input, $multiplier)
 Array Repeat. More...
 
 _base256_lshift (&$x, $shift)
 Logical Left Shift. More...
 
 _base256_rshift (&$x, $shift)
 Logical Right Shift. More...
 
 _int2bytes ($x)
 Converts 32-bit integers to bytes. More...
 
 _bytes2int ($x)
 Converts bytes to 32-bit integers. More...
 
 _encodeASN1Length ($length)
 DER-encode an integer. More...
 
 _safe_divide ($x, $y)
 Single digit division. More...
 

Data Fields

const MONTGOMERY = 0
 #+ Reduction constants More...
 
const BARRETT = 1
 
const POWEROF2 = 2
 
const CLASSIC = 3
 
const NONE = 4
 
const VALUE = 0
 #- More...
 
const SIGN = 1
 $result[self::SIGN] contains the sign. More...
 
const VARIABLE = 0
 #- More...
 
const DATA = 1
 $cache[self::DATA] contains the cached data. More...
 
const MODE_INTERNAL = 1
 #- More...
 
const MODE_BCMATH = 2
 To use the BCMath library. More...
 
const MODE_GMP = 3
 To use the GMP library. More...
 
const KARATSUBA_CUTOFF = 25
 #- More...
 
 $value
 
 $is_negative = false
 
 $precision = -1
 Precision. More...
 
 $bitmask = false
 Precision Bitmask. More...
 
 $hex
 

Static Protected Attributes

static $base
 #+ Static properties used by the pure-PHP implementation. More...
 
static $baseFull
 
static $maxDigit
 
static $msb
 
static $max10
 $max10 in greatest $max10Len satisfying $max10 = 10**$max10Len <= 2**$base. More...
 
static $max10Len
 $max10Len in greatest $max10Len satisfying $max10 = 10**$max10Len <= 2**$base. More...
 
static $maxDigit2
 

Detailed Description

Definition at line 63 of file BigInteger.php.

Constructor & Destructor Documentation

◆ __construct()

phpseclib\Math\BigInteger::__construct (   $x = 0,
  $base = 10 
)

Converts base-2, base-10, base-16, and binary strings (base-256) to BigIntegers.

If the second parameter - $base - is negative, then it will be assumed that the number's are encoded using two's compliment. The sole exception to this is -10, which is treated the same as 10 is.

Here's an example: <?php $a = new \phpseclib\Math\BigInteger('0x32', 16); // 50 in base-16

echo $a->toString(); // outputs 50 ?>

Parameters
$xbase-10 number or base-$base number if $base set.
int$base
Returns
\phpseclib\Math\BigInteger @access public

Definition at line 252 of file BigInteger.php.

253 {
254 if (!defined('MATH_BIGINTEGER_MODE')) {
255 switch (true) {
256 case extension_loaded('gmp'):
257 define('MATH_BIGINTEGER_MODE', self::MODE_GMP);
258 break;
259 case extension_loaded('bcmath'):
260 define('MATH_BIGINTEGER_MODE', self::MODE_BCMATH);
261 break;
262 default:
263 define('MATH_BIGINTEGER_MODE', self::MODE_INTERNAL);
264 }
265 }
266
267 if (extension_loaded('openssl') && !defined('MATH_BIGINTEGER_OPENSSL_DISABLE') && !defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
268 // some versions of XAMPP have mismatched versions of OpenSSL which causes it not to work
269 ob_start();
270 @phpinfo();
271 $content = ob_get_contents();
272 ob_end_clean();
273
274 preg_match_all('#OpenSSL (Header|Library) Version(.*)#im', $content, $matches);
275
276 $versions = array();
277 if (!empty($matches[1])) {
278 for ($i = 0; $i < count($matches[1]); $i++) {
279 $fullVersion = trim(str_replace('=>', '', strip_tags($matches[2][$i])));
280
281 // Remove letter part in OpenSSL version
282 if (!preg_match('/(\d+\.\d+\.\d+)/i', $fullVersion, $m)) {
283 $versions[$matches[1][$i]] = $fullVersion;
284 } else {
285 $versions[$matches[1][$i]] = $m[0];
286 }
287 }
288 }
289
290 // it doesn't appear that OpenSSL versions were reported upon until PHP 5.3+
291 switch (true) {
292 case !isset($versions['Header']):
293 case !isset($versions['Library']):
294 case $versions['Header'] == $versions['Library']:
295 define('MATH_BIGINTEGER_OPENSSL_ENABLED', true);
296 break;
297 default:
298 define('MATH_BIGINTEGER_OPENSSL_DISABLE', true);
299 }
300 }
301
302 if (!defined('PHP_INT_SIZE')) {
303 define('PHP_INT_SIZE', 4);
304 }
305
306 if (empty(self::$base) && MATH_BIGINTEGER_MODE == self::MODE_INTERNAL) {
307 switch (PHP_INT_SIZE) {
308 case 8: // use 64-bit integers if int size is 8 bytes
309 self::$base = 31;
310 self::$baseFull = 0x80000000;
311 self::$maxDigit = 0x7FFFFFFF;
312 self::$msb = 0x40000000;
313 self::$max10 = 1000000000;
314 self::$max10Len = 9;
315 self::$maxDigit2 = pow(2, 62);
316 break;
317 //case 4: // use 64-bit floats if int size is 4 bytes
318 default:
319 self::$base = 26;
320 self::$baseFull = 0x4000000;
321 self::$maxDigit = 0x3FFFFFF;
322 self::$msb = 0x2000000;
323 self::$max10 = 10000000;
324 self::$max10Len = 7;
325 self::$maxDigit2 = pow(2, 52); // pow() prevents truncation
326 }
327 }
328
329 switch (MATH_BIGINTEGER_MODE) {
330 case self::MODE_GMP:
331 switch (true) {
332 case is_resource($x) && get_resource_type($x) == 'GMP integer':
333 // PHP 5.6 switched GMP from using resources to objects
334 case $x instanceof \GMP:
335 $this->value = $x;
336 return;
337 }
338 $this->value = gmp_init(0);
339 break;
341 $this->value = '0';
342 break;
343 default:
344 $this->value = array();
345 }
346
347 // '0' counts as empty() but when the base is 256 '0' is equal to ord('0') or 48
348 // '0' is the only value like this per http://php.net/empty
349 if (empty($x) && (abs($base) != 256 || $x !== '0')) {
350 return;
351 }
352
353 switch ($base) {
354 case -256:
355 if (ord($x[0]) & 0x80) {
356 $x = ~$x;
357 $this->is_negative = true;
358 }
359 case 256:
360 switch (MATH_BIGINTEGER_MODE) {
361 case self::MODE_GMP:
362 $sign = $this->is_negative ? '-' : '';
363 $this->value = gmp_init($sign . '0x' . bin2hex($x));
364 break;
366 // round $len to the nearest 4 (thanks, DavidMJ!)
367 $len = (strlen($x) + 3) & 0xFFFFFFFC;
368
369 $x = str_pad($x, $len, chr(0), STR_PAD_LEFT);
370
371 for ($i = 0; $i < $len; $i+= 4) {
372 $this->value = bcmul($this->value, '4294967296', 0); // 4294967296 == 2**32
373 $this->value = bcadd($this->value, 0x1000000 * ord($x[$i]) + ((ord($x[$i + 1]) << 16) | (ord($x[$i + 2]) << 8) | ord($x[$i + 3])), 0);
374 }
375
376 if ($this->is_negative) {
377 $this->value = '-' . $this->value;
378 }
379
380 break;
381 // converts a base-2**8 (big endian / msb) number to base-2**26 (little endian / lsb)
382 default:
383 while (strlen($x)) {
384 $this->value[] = $this->_bytes2int($this->_base256_rshift($x, self::$base));
385 }
386 }
387
388 if ($this->is_negative) {
389 if (MATH_BIGINTEGER_MODE != self::MODE_INTERNAL) {
390 $this->is_negative = false;
391 }
392 $temp = $this->add(new static('-1'));
393 $this->value = $temp->value;
394 }
395 break;
396 case 16:
397 case -16:
398 if ($base > 0 && $x[0] == '-') {
399 $this->is_negative = true;
400 $x = substr($x, 1);
401 }
402
403 $x = preg_replace('#^(?:0x)?([A-Fa-f0-9]*).*#', '$1', $x);
404
405 $is_negative = false;
406 if ($base < 0 && hexdec($x[0]) >= 8) {
407 $this->is_negative = $is_negative = true;
408 $x = bin2hex(~pack('H*', $x));
409 }
410
411 switch (MATH_BIGINTEGER_MODE) {
412 case self::MODE_GMP:
413 $temp = $this->is_negative ? '-0x' . $x : '0x' . $x;
414 $this->value = gmp_init($temp);
415 $this->is_negative = false;
416 break;
418 $x = (strlen($x) & 1) ? '0' . $x : $x;
419 $temp = new static(pack('H*', $x), 256);
420 $this->value = $this->is_negative ? '-' . $temp->value : $temp->value;
421 $this->is_negative = false;
422 break;
423 default:
424 $x = (strlen($x) & 1) ? '0' . $x : $x;
425 $temp = new static(pack('H*', $x), 256);
426 $this->value = $temp->value;
427 }
428
429 if ($is_negative) {
430 $temp = $this->add(new static('-1'));
431 $this->value = $temp->value;
432 }
433 break;
434 case 10:
435 case -10:
436 // (?<!^)(?:-).*: find any -'s that aren't at the beginning and then any characters that follow that
437 // (?<=^|-)0*: find any 0's that are preceded by the start of the string or by a - (ie. octals)
438 // [^-0-9].*: find any non-numeric characters and then any characters that follow that
439 $x = preg_replace('#(?<!^)(?:-).*|(?<=^|-)0*|[^-0-9].*#', '', $x);
440
441 switch (MATH_BIGINTEGER_MODE) {
442 case self::MODE_GMP:
443 $this->value = gmp_init($x);
444 break;
446 // explicitly casting $x to a string is necessary, here, since doing $x[0] on -1 yields different
447 // results then doing it on '-1' does (modInverse does $x[0])
448 $this->value = $x === '-' ? '0' : (string) $x;
449 break;
450 default:
451 $temp = new static();
452
453 $multiplier = new static();
454 $multiplier->value = array(self::$max10);
455
456 if ($x[0] == '-') {
457 $this->is_negative = true;
458 $x = substr($x, 1);
459 }
460
461 $x = str_pad($x, strlen($x) + ((self::$max10Len - 1) * strlen($x)) % self::$max10Len, 0, STR_PAD_LEFT);
462 while (strlen($x)) {
463 $temp = $temp->multiply($multiplier);
464 $temp = $temp->add(new static($this->_int2bytes(substr($x, 0, self::$max10Len)), 256));
465 $x = substr($x, self::$max10Len);
466 }
467
468 $this->value = $temp->value;
469 }
470 break;
471 case 2: // base-2 support originally implemented by Lluis Pamies - thanks!
472 case -2:
473 if ($base > 0 && $x[0] == '-') {
474 $this->is_negative = true;
475 $x = substr($x, 1);
476 }
477
478 $x = preg_replace('#^([01]*).*#', '$1', $x);
479 $x = str_pad($x, strlen($x) + (3 * strlen($x)) % 4, 0, STR_PAD_LEFT);
480
481 $str = '0x';
482 while (strlen($x)) {
483 $part = substr($x, 0, 4);
484 $str.= dechex(bindec($part));
485 $x = substr($x, 4);
486 }
487
488 if ($this->is_negative) {
489 $str = '-' . $str;
490 }
491
492 $temp = new static($str, 8 * $base); // ie. either -16 or +16
493 $this->value = $temp->value;
494 $this->is_negative = $temp->is_negative;
495
496 break;
497 default:
498 // base not supported, so we'll let $this == 0
499 }
500 }
add($y)
Adds two BigIntegers.
Definition: BigInteger.php:859
const MODE_GMP
To use the GMP library.
Definition: BigInteger.php:150
_bytes2int($x)
Converts bytes to 32-bit integers.
static $base
#+ Static properties used by the pure-PHP implementation.
Definition: BigInteger.php:167
abs()
Absolute value.
const MODE_BCMATH
To use the BCMath library.
Definition: BigInteger.php:144
_base256_rshift(&$x, $shift)
Logical Right Shift.
_int2bytes($x)
Converts 32-bit integers to bytes.
$x
Definition: complexTest.php:9
$i
Definition: disco.tpl.php:19
$base
Definition: index.php:4

References $base, phpseclib\Math\BigInteger\$base, $i, phpseclib\Math\BigInteger\$is_negative, $m, phpseclib\Math\BigInteger\$value, $x, phpseclib\Math\BigInteger\_base256_rshift(), phpseclib\Math\BigInteger\_bytes2int(), phpseclib\Math\BigInteger\_int2bytes(), phpseclib\Math\BigInteger\abs(), phpseclib\Math\BigInteger\add(), phpseclib\Math\BigInteger\MODE_BCMATH, and phpseclib\Math\BigInteger\MODE_GMP.

+ Here is the call graph for this function:

Member Function Documentation

◆ __clone()

phpseclib\Math\BigInteger::__clone ( )

__clone() magic method

Although you can call BigInteger::__toString() directly in PHP5, you cannot call BigInteger::__clone() 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 only syntax of $y = clone $x. As such, if you're trying to write an application that works on both PHP4 and PHP5, call BigInteger::copy(), instead.

@access public

See also
self::copy()
Returns
\phpseclib\Math\BigInteger

Definition at line 764 of file BigInteger.php.

765 {
766 return $this->copy();
767 }
copy()
Copy an object.
Definition: BigInteger.php:728

References phpseclib\Math\BigInteger\copy().

+ Here is the call graph for this function:

◆ __debugInfo()

phpseclib\Math\BigInteger::__debugInfo ( )

__debugInfo() magic method

Will be called, automatically, when print_r() or var_dump() are called

@access public

Definition at line 813 of file BigInteger.php.

814 {
815 $opts = array();
816 switch (MATH_BIGINTEGER_MODE) {
817 case self::MODE_GMP:
818 $engine = 'gmp';
819 break;
821 $engine = 'bcmath';
822 break;
824 $engine = 'internal';
825 $opts[] = PHP_INT_SIZE == 8 ? '64-bit' : '32-bit';
826 }
827 if (MATH_BIGINTEGER_MODE != self::MODE_GMP && defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
828 $opts[] = 'OpenSSL';
829 }
830 if (!empty($opts)) {
831 $engine.= ' (' . implode($opts, ', ') . ')';
832 }
833 return array(
834 'value' => '0x' . $this->toHex(true),
835 'engine' => $engine
836 );
837 }
toHex($twos_compliment=false)
Converts a BigInteger to a hex string (eg.
Definition: BigInteger.php:617
$engine
Definition: workflow.php:89

References $engine, phpseclib\Math\BigInteger\MODE_BCMATH, phpseclib\Math\BigInteger\MODE_GMP, phpseclib\Math\BigInteger\MODE_INTERNAL, and phpseclib\Math\BigInteger\toHex().

+ Here is the call graph for this function:

◆ __sleep()

phpseclib\Math\BigInteger::__sleep ( )

__sleep() magic method

Will be called, automatically, when serialize() is called on a BigInteger object.

See also
self::__wakeup() @access User interface

Definition at line 777 of file BigInteger.php.

778 {
779 $this->hex = $this->toHex(true);
780 $vars = array('hex');
781 if ($this->precision > 0) {
782 $vars[] = 'precision';
783 }
784 return $vars;
785 }

References phpseclib\Math\BigInteger\toHex().

+ Here is the call graph for this function:

◆ __toString()

phpseclib\Math\BigInteger::__toString ( )

__toString() magic method

Will be called, automatically, if you're supporting just PHP5. If you're supporting PHP4, you'll need to call toString().

@access public

Definition at line 747 of file BigInteger.php.

748 {
749 return $this->toString();
750 }
toString()
Converts a BigInteger to a base-10 number.
Definition: BigInteger.php:677

References phpseclib\Math\BigInteger\toString().

+ Here is the call graph for this function:

◆ __wakeup()

phpseclib\Math\BigInteger::__wakeup ( )

__wakeup() magic method

Will be called, automatically, when unserialize() is called on a BigInteger object.

See also
self::__sleep() @access User interface

Definition at line 795 of file BigInteger.php.

796 {
797 $temp = new static($this->hex, -16);
798 $this->value = $temp->value;
799 $this->is_negative = $temp->is_negative;
800 if ($this->precision > 0) {
801 // recalculate $this->bitmask
802 $this->setPrecision($this->precision);
803 }
804 }
setPrecision($bits)
Set Precision.

References phpseclib\Math\BigInteger\$hex, and phpseclib\Math\BigInteger\setPrecision().

+ Here is the call graph for this function:

◆ _add()

phpseclib\Math\BigInteger::_add (   $x_value,
  $x_negative,
  $y_value,
  $y_negative 
)

Performs addition.

Parameters
array$x_value
bool$x_negative
array$y_value
bool$y_negative
Returns
array @access private

Definition at line 893 of file BigInteger.php.

894 {
895 $x_size = count($x_value);
896 $y_size = count($y_value);
897
898 if ($x_size == 0) {
899 return array(
900 self::VALUE => $y_value,
901 self::SIGN => $y_negative
902 );
903 } elseif ($y_size == 0) {
904 return array(
905 self::VALUE => $x_value,
906 self::SIGN => $x_negative
907 );
908 }
909
910 // subtract, if appropriate
911 if ($x_negative != $y_negative) {
912 if ($x_value == $y_value) {
913 return array(
914 self::VALUE => array(),
915 self::SIGN => false
916 );
917 }
918
919 $temp = $this->_subtract($x_value, false, $y_value, false);
920 $temp[self::SIGN] = $this->_compare($x_value, false, $y_value, false) > 0 ?
921 $x_negative : $y_negative;
922
923 return $temp;
924 }
925
926 if ($x_size < $y_size) {
927 $size = $x_size;
928 $value = $y_value;
929 } else {
930 $size = $y_size;
931 $value = $x_value;
932 }
933
934 $value[count($value)] = 0; // just in case the carry adds an extra digit
935
936 $carry = 0;
937 for ($i = 0, $j = 1; $j < $size; $i+=2, $j+=2) {
938 $sum = $x_value[$j] * self::$baseFull + $x_value[$i] + $y_value[$j] * self::$baseFull + $y_value[$i] + $carry;
939 $carry = $sum >= self::$maxDigit2; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1
940 $sum = $carry ? $sum - self::$maxDigit2 : $sum;
941
942 $temp = self::$base === 26 ? intval($sum / 0x4000000) : ($sum >> 31);
943
944 $value[$i] = (int) ($sum - self::$baseFull * $temp); // eg. a faster alternative to fmod($sum, 0x4000000)
945 $value[$j] = $temp;
946 }
947
948 if ($j == $size) { // ie. if $y_size is odd
949 $sum = $x_value[$i] + $y_value[$i] + $carry;
950 $carry = $sum >= self::$baseFull;
951 $value[$i] = $carry ? $sum - self::$baseFull : $sum;
952 ++$i; // ie. let $i = $j since we've just done $value[$i]
953 }
954
955 if ($carry) {
956 for (; $value[$i] == self::$maxDigit; ++$i) {
957 $value[$i] = 0;
958 }
959 ++$value[$i];
960 }
961
962 return array(
963 self::VALUE => $this->_trim($value),
964 self::SIGN => $x_negative
965 );
966 }
$size
Definition: RandomTest.php:84
_subtract($x_value, $x_negative, $y_value, $y_negative)
Performs subtraction.
const SIGN
$result[self::SIGN] contains the sign.
Definition: BigInteger.php:109
_compare($x_value, $x_negative, $y_value, $y_negative)
Compares two numbers.

References $base, phpseclib\Math\BigInteger\$baseFull, $i, phpseclib\Math\BigInteger\$maxDigit, phpseclib\Math\BigInteger\$maxDigit2, $size, phpseclib\Math\BigInteger\$value, phpseclib\Math\BigInteger\_compare(), phpseclib\Math\BigInteger\_subtract(), phpseclib\Math\BigInteger\_trim(), and phpseclib\Math\BigInteger\SIGN.

Referenced by phpseclib\Math\BigInteger\_barrett(), phpseclib\Math\BigInteger\_karatsuba(), phpseclib\Math\BigInteger\_karatsubaSquare(), phpseclib\Math\BigInteger\_montgomery(), phpseclib\Math\BigInteger\_montgomeryMultiply(), phpseclib\Math\BigInteger\_regularBarrett(), phpseclib\Math\BigInteger\_subtract(), and phpseclib\Math\BigInteger\add().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ _array_repeat()

phpseclib\Math\BigInteger::_array_repeat (   $input,
  $multiplier 
)

Array Repeat.

Parameters
$inputArray
$multipliermixed
Returns
array @access private

Definition at line 3609 of file BigInteger.php.

3610 {
3611 return ($multiplier) ? array_fill(0, $multiplier, $input) : array();
3612 }

References $input.

Referenced by phpseclib\Math\BigInteger\_barrett(), phpseclib\Math\BigInteger\_baseSquare(), phpseclib\Math\BigInteger\_montgomery(), phpseclib\Math\BigInteger\_montgomeryMultiply(), phpseclib\Math\BigInteger\_multiplyLower(), phpseclib\Math\BigInteger\_prepMontgomery(), phpseclib\Math\BigInteger\_regularBarrett(), phpseclib\Math\BigInteger\_regularMultiply(), and phpseclib\Math\BigInteger\divide().

+ Here is the caller graph for this function:

◆ _barrett()

phpseclib\Math\BigInteger::_barrett (   $n,
  $m 
)

Barrett Modular Reduction.

See HAC 14.3.3 / MPM 6.2.5 for more information. Modified slightly, so as not to require negative numbers (initially, this script didn't support negative numbers).

Employs "folding", as described at thesis-149.pdf#page=66. To quote from 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."

Unfortunately, the "Barrett Reduction with Folding" algorithm described in thesis-149.pdf is not, as written, all that usable on account of (1) its not using reasonable radix points as discussed in MPM 6.2.2 and (2) the fact that, even with reasonable radix points, it only works when there are an even number of digits in the denominator. The reason for (2) is that (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 comments for details.

See also
self::_slidingWindow() @access private
Parameters
array$n
array$m
Returns
array

Definition at line 2013 of file BigInteger.php.

2014 {
2015 static $cache = array(
2016 self::VARIABLE => array(),
2017 self::DATA => array()
2018 );
2019
2020 $m_length = count($m);
2021
2022 // if ($this->_compare($n, $this->_square($m)) >= 0) {
2023 if (count($n) > 2 * $m_length) {
2024 $lhs = new static();
2025 $rhs = new static();
2026 $lhs->value = $n;
2027 $rhs->value = $m;
2028 list(, $temp) = $lhs->divide($rhs);
2029 return $temp->value;
2030 }
2031
2032 // if (m.length >> 1) + 2 <= m.length then m is too small and n can't be reduced
2033 if ($m_length < 5) {
2034 return $this->_regularBarrett($n, $m);
2035 }
2036
2037 // n = 2 * m.length
2038
2039 if (($key = array_search($m, $cache[self::VARIABLE])) === false) {
2040 $key = count($cache[self::VARIABLE]);
2041 $cache[self::VARIABLE][] = $m;
2042
2043 $lhs = new static();
2044 $lhs_value = &$lhs->value;
2045 $lhs_value = $this->_array_repeat(0, $m_length + ($m_length >> 1));
2046 $lhs_value[] = 1;
2047 $rhs = new static();
2048 $rhs->value = $m;
2049
2050 list($u, $m1) = $lhs->divide($rhs);
2051 $u = $u->value;
2052 $m1 = $m1->value;
2053
2054 $cache[self::DATA][] = array(
2055 'u' => $u, // m.length >> 1 (technically (m.length >> 1) + 1)
2056 'm1'=> $m1 // m.length
2057 );
2058 } else {
2059 extract($cache[self::DATA][$key]);
2060 }
2061
2062 $cutoff = $m_length + ($m_length >> 1);
2063 $lsd = array_slice($n, 0, $cutoff); // m.length + (m.length >> 1)
2064 $msd = array_slice($n, $cutoff); // m.length >> 1
2065 $lsd = $this->_trim($lsd);
2066 $temp = $this->_multiply($msd, false, $m1, false);
2067 $n = $this->_add($lsd, false, $temp[self::VALUE], false); // m.length + (m.length >> 1) + 1
2068
2069 if ($m_length & 1) {
2070 return $this->_regularBarrett($n[self::VALUE], $m);
2071 }
2072
2073 // (m.length + (m.length >> 1) + 1) - (m.length - 1) == (m.length >> 1) + 2
2074 $temp = array_slice($n[self::VALUE], $m_length - 1);
2075 // if even: ((m.length >> 1) + 2) + (m.length >> 1) == m.length + 2
2076 // if odd: ((m.length >> 1) + 2) + (m.length >> 1) == (m.length - 1) + 2 == m.length + 1
2077 $temp = $this->_multiply($temp, false, $u, false);
2078 // if even: (m.length + 2) - ((m.length >> 1) + 1) = m.length - (m.length >> 1) + 1
2079 // if odd: (m.length + 1) - ((m.length >> 1) + 1) = m.length - (m.length >> 1)
2080 $temp = array_slice($temp[self::VALUE], ($m_length >> 1) + 1);
2081 // if even: (m.length - (m.length >> 1) + 1) + m.length = 2 * m.length - (m.length >> 1) + 1
2082 // if odd: (m.length - (m.length >> 1)) + m.length = 2 * m.length - (m.length >> 1)
2083 $temp = $this->_multiply($temp, false, $m, false);
2084
2085 // at this point, if m had an odd number of digits, we'd be subtracting a 2 * m.length - (m.length >> 1) digit
2086 // number from a m.length + (m.length >> 1) + 1 digit number. ie. there'd be an extra digit and the while loop
2087 // following this comment would loop a lot (hence our calling _regularBarrett() in that situation).
2088
2089 $result = $this->_subtract($n[self::VALUE], false, $temp[self::VALUE], false);
2090
2091 while ($this->_compare($result[self::VALUE], $result[self::SIGN], $m, false) >= 0) {
2092 $result = $this->_subtract($result[self::VALUE], $result[self::SIGN], $m, false);
2093 }
2094
2095 return $result[self::VALUE];
2096 }
$result
$n
Definition: RandomTest.php:85
const DATA
$cache[self::DATA] contains the cached data.
Definition: BigInteger.php:126
_array_repeat($input, $multiplier)
Array Repeat.
_multiply($x_value, $x_negative, $y_value, $y_negative)
Performs multiplication.
_add($x_value, $x_negative, $y_value, $y_negative)
Performs addition.
Definition: BigInteger.php:893
_regularBarrett($x, $n)
(Regular) Barrett Modular Reduction
$key
Definition: croninfo.php:18

References $key, $m, $n, $result, phpseclib\Math\BigInteger\_add(), phpseclib\Math\BigInteger\_array_repeat(), phpseclib\Math\BigInteger\_compare(), phpseclib\Math\BigInteger\_multiply(), phpseclib\Math\BigInteger\_regularBarrett(), phpseclib\Math\BigInteger\_subtract(), phpseclib\Math\BigInteger\_trim(), phpseclib\Math\BigInteger\DATA, phpseclib\Math\BigInteger\VALUE, and phpseclib\Math\BigInteger\VARIABLE.

Referenced by phpseclib\Math\BigInteger\_reduce().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ _base256_lshift()

phpseclib\Math\BigInteger::_base256_lshift ( $x,
  $shift 
)

Logical Left Shift.

Shifts binary strings $shift bits, essentially multiplying by 2**$shift.

Parameters
$xString
$shiftInteger
Returns
string @access private

Definition at line 3624 of file BigInteger.php.

3625 {
3626 if ($shift == 0) {
3627 return;
3628 }
3629
3630 $num_bytes = $shift >> 3; // eg. floor($shift/8)
3631 $shift &= 7; // eg. $shift % 8
3632
3633 $carry = 0;
3634 for ($i = strlen($x) - 1; $i >= 0; --$i) {
3635 $temp = ord($x[$i]) << $shift | $carry;
3636 $x[$i] = chr($temp);
3637 $carry = $temp >> 8;
3638 }
3639 $carry = ($carry != 0) ? chr($carry) : '';
3640 $x = $carry . $x . str_repeat(chr(0), $num_bytes);
3641 }

References $i, and $x.

Referenced by phpseclib\Math\BigInteger\bitwise_not().

+ Here is the caller graph for this function:

◆ _base256_rshift()

phpseclib\Math\BigInteger::_base256_rshift ( $x,
  $shift 
)

Logical Right Shift.

Shifts binary strings $shift bits, essentially dividing by 2**$shift and returning the remainder.

Parameters
$xString
$shiftInteger
Returns
string @access private

Definition at line 3653 of file BigInteger.php.

3654 {
3655 if ($shift == 0) {
3656 $x = ltrim($x, chr(0));
3657 return '';
3658 }
3659
3660 $num_bytes = $shift >> 3; // eg. floor($shift/8)
3661 $shift &= 7; // eg. $shift % 8
3662
3663 $remainder = '';
3664 if ($num_bytes) {
3665 $start = $num_bytes > strlen($x) ? -strlen($x) : -$num_bytes;
3666 $remainder = substr($x, $start);
3667 $x = substr($x, 0, -$num_bytes);
3668 }
3669
3670 $carry = 0;
3671 $carry_shift = 8 - $shift;
3672 for ($i = 0; $i < strlen($x); ++$i) {
3673 $temp = (ord($x[$i]) >> $shift) | $carry;
3674 $carry = (ord($x[$i]) << $carry_shift) & 0xFF;
3675 $x[$i] = chr($temp);
3676 }
3677 $x = ltrim($x, chr(0));
3678
3679 $remainder = chr($carry >> $carry_shift) . $remainder;
3680
3681 return ltrim($remainder, chr(0));
3682 }
$start
Definition: bench.php:8

References $i, $start, and $x.

Referenced by phpseclib\Math\BigInteger\__construct().

+ Here is the caller graph for this function:

◆ _baseSquare()

phpseclib\Math\BigInteger::_baseSquare (   $value)

Performs traditional squaring on two BigIntegers.

Squaring can be done faster than multiplying a number by itself can be. See HAC 14.2.4 / MPM 5.3 for more information.

Parameters
array$value
Returns
array @access private

Definition at line 1312 of file BigInteger.php.

1313 {
1314 if (empty($value)) {
1315 return array();
1316 }
1317 $square_value = $this->_array_repeat(0, 2 * count($value));
1318
1319 for ($i = 0, $max_index = count($value) - 1; $i <= $max_index; ++$i) {
1320 $i2 = $i << 1;
1321
1322 $temp = $square_value[$i2] + $value[$i] * $value[$i];
1323 $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
1324 $square_value[$i2] = (int) ($temp - self::$baseFull * $carry);
1325
1326 // note how we start from $i+1 instead of 0 as we do in multiplication.
1327 for ($j = $i + 1, $k = $i2 + 1; $j <= $max_index; ++$j, ++$k) {
1328 $temp = $square_value[$k] + 2 * $value[$j] * $value[$i] + $carry;
1329 $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
1330 $square_value[$k] = (int) ($temp - self::$baseFull * $carry);
1331 }
1332
1333 // the following line can yield values larger 2**15. at this point, PHP should switch
1334 // over to floats.
1335 $square_value[$i + $max_index + 1] = $carry;
1336 }
1337
1338 return $square_value;
1339 }

References $base, $i, phpseclib\Math\BigInteger\$value, and phpseclib\Math\BigInteger\_array_repeat().

Referenced by phpseclib\Math\BigInteger\_karatsubaSquare(), and phpseclib\Math\BigInteger\_square().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ _bytes2int()

phpseclib\Math\BigInteger::_bytes2int (   $x)

Converts bytes to 32-bit integers.

Parameters
string$x
Returns
int @access private

Definition at line 3706 of file BigInteger.php.

3707 {
3708 $temp = unpack('Nint', str_pad($x, 4, chr(0), STR_PAD_LEFT));
3709 return $temp['int'];
3710 }

References $x.

Referenced by phpseclib\Math\BigInteger\__construct().

+ Here is the caller graph for this function:

◆ _compare()

phpseclib\Math\BigInteger::_compare (   $x_value,
  $x_negative,
  $y_value,
  $y_negative 
)

Compares two numbers.

Parameters
array$x_value
bool$x_negative
array$y_value
bool$y_negative
Returns
int
See also
self::compare() @access private

Definition at line 2701 of file BigInteger.php.

2702 {
2703 if ($x_negative != $y_negative) {
2704 return (!$x_negative && $y_negative) ? 1 : -1;
2705 }
2706
2707 $result = $x_negative ? -1 : 1;
2708
2709 if (count($x_value) != count($y_value)) {
2710 return (count($x_value) > count($y_value)) ? $result : -$result;
2711 }
2712 $size = max(count($x_value), count($y_value));
2713
2714 $x_value = array_pad($x_value, $size, 0);
2715 $y_value = array_pad($y_value, $size, 0);
2716
2717 for ($i = count($x_value) - 1; $i >= 0; --$i) {
2718 if ($x_value[$i] != $y_value[$i]) {
2719 return ($x_value[$i] > $y_value[$i]) ? $result : -$result;
2720 }
2721 }
2722
2723 return 0;
2724 }

References $i, $result, and $size.

Referenced by phpseclib\Math\BigInteger\_add(), phpseclib\Math\BigInteger\_barrett(), phpseclib\Math\BigInteger\_montgomery(), phpseclib\Math\BigInteger\_montgomeryMultiply(), phpseclib\Math\BigInteger\_regularBarrett(), phpseclib\Math\BigInteger\_subtract(), and phpseclib\Math\BigInteger\compare().

+ Here is the caller graph for this function:

◆ _divide_digit()

phpseclib\Math\BigInteger::_divide_digit (   $dividend,
  $divisor 
)

Divides a BigInteger by a regular integer.

abc / x = a00 / x + b0 / x + c / x

Parameters
array$dividend
array$divisor
Returns
array @access private

Definition at line 1587 of file BigInteger.php.

1588 {
1589 $carry = 0;
1590 $result = array();
1591
1592 for ($i = count($dividend) - 1; $i >= 0; --$i) {
1593 $temp = self::$baseFull * $carry + $dividend[$i];
1594 $result[$i] = $this->_safe_divide($temp, $divisor);
1595 $carry = (int) ($temp - $divisor * $result[$i]);
1596 }
1597
1598 return array($result, $carry);
1599 }
_safe_divide($x, $y)
Single digit division.

References $i, $result, and phpseclib\Math\BigInteger\_safe_divide().

Referenced by phpseclib\Math\BigInteger\divide(), and phpseclib\Math\BigInteger\isPrime().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ _encodeASN1Length()

phpseclib\Math\BigInteger::_encodeASN1Length (   $length)

DER-encode an integer.

The ability to DER-encode integers is needed to create RSA public keys for use with OpenSSL

See also
self::modPow() @access private
Parameters
int$length
Returns
string

Definition at line 3722 of file BigInteger.php.

3723 {
3724 if ($length <= 0x7F) {
3725 return chr($length);
3726 }
3727
3728 $temp = ltrim(pack('N', $length), chr(0));
3729 return pack('Ca*', 0x80 | strlen($temp), $temp);
3730 }

Referenced by phpseclib\Math\BigInteger\modPow().

+ Here is the caller graph for this function:

◆ _int2bytes()

phpseclib\Math\BigInteger::_int2bytes (   $x)

Converts 32-bit integers to bytes.

Parameters
int$x
Returns
string @access private

Definition at line 3694 of file BigInteger.php.

3695 {
3696 return ltrim(pack('N', $x), chr(0));
3697 }

References $x.

Referenced by phpseclib\Math\BigInteger\__construct(), and phpseclib\Math\BigInteger\toBytes().

+ Here is the caller graph for this function:

◆ _karatsuba()

phpseclib\Math\BigInteger::_karatsuba (   $x_value,
  $y_value 
)

Performs Karatsuba multiplication on two BigIntegers.

See Karatsuba algorithm and MPM 5.2.3.

Parameters
array$x_value
array$y_value
Returns
array @access private

Definition at line 1256 of file BigInteger.php.

1257 {
1258 $m = min(count($x_value) >> 1, count($y_value) >> 1);
1259
1260 if ($m < self::KARATSUBA_CUTOFF) {
1261 return $this->_regularMultiply($x_value, $y_value);
1262 }
1263
1264 $x1 = array_slice($x_value, $m);
1265 $x0 = array_slice($x_value, 0, $m);
1266 $y1 = array_slice($y_value, $m);
1267 $y0 = array_slice($y_value, 0, $m);
1268
1269 $z2 = $this->_karatsuba($x1, $y1);
1270 $z0 = $this->_karatsuba($x0, $y0);
1271
1272 $z1 = $this->_add($x1, false, $x0, false);
1273 $temp = $this->_add($y1, false, $y0, false);
1274 $z1 = $this->_karatsuba($z1[self::VALUE], $temp[self::VALUE]);
1275 $temp = $this->_add($z2, false, $z0, false);
1276 $z1 = $this->_subtract($z1, false, $temp[self::VALUE], false);
1277
1278 $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2);
1279 $z1[self::VALUE] = array_merge(array_fill(0, $m, 0), $z1[self::VALUE]);
1280
1281 $xy = $this->_add($z2, false, $z1[self::VALUE], $z1[self::SIGN]);
1282 $xy = $this->_add($xy[self::VALUE], $xy[self::SIGN], $z0, false);
1283
1284 return $xy[self::VALUE];
1285 }
_karatsuba($x_value, $y_value)
Performs Karatsuba multiplication on two BigIntegers.
_regularMultiply($x_value, $y_value)
Performs long multiplication on two BigIntegers.

References $m, phpseclib\Math\BigInteger\_add(), phpseclib\Math\BigInteger\_karatsuba(), phpseclib\Math\BigInteger\_regularMultiply(), phpseclib\Math\BigInteger\_subtract(), and phpseclib\Math\BigInteger\VALUE.

Referenced by phpseclib\Math\BigInteger\_karatsuba(), and phpseclib\Math\BigInteger\_multiply().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ _karatsubaSquare()

phpseclib\Math\BigInteger::_karatsubaSquare (   $value)

Performs Karatsuba "squaring" on two BigIntegers.

See Karatsuba algorithm and MPM 5.3.4.

Parameters
array$value
Returns
array @access private

Definition at line 1351 of file BigInteger.php.

1352 {
1353 $m = count($value) >> 1;
1354
1355 if ($m < self::KARATSUBA_CUTOFF) {
1356 return $this->_baseSquare($value);
1357 }
1358
1359 $x1 = array_slice($value, $m);
1360 $x0 = array_slice($value, 0, $m);
1361
1362 $z2 = $this->_karatsubaSquare($x1);
1363 $z0 = $this->_karatsubaSquare($x0);
1364
1365 $z1 = $this->_add($x1, false, $x0, false);
1366 $z1 = $this->_karatsubaSquare($z1[self::VALUE]);
1367 $temp = $this->_add($z2, false, $z0, false);
1368 $z1 = $this->_subtract($z1, false, $temp[self::VALUE], false);
1369
1370 $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2);
1371 $z1[self::VALUE] = array_merge(array_fill(0, $m, 0), $z1[self::VALUE]);
1372
1373 $xx = $this->_add($z2, false, $z1[self::VALUE], $z1[self::SIGN]);
1374 $xx = $this->_add($xx[self::VALUE], $xx[self::SIGN], $z0, false);
1375
1376 return $xx[self::VALUE];
1377 }
_karatsubaSquare($value)
Performs Karatsuba "squaring" on two BigIntegers.
_baseSquare($value)
Performs traditional squaring on two BigIntegers.

References $m, phpseclib\Math\BigInteger\$value, phpseclib\Math\BigInteger\_add(), phpseclib\Math\BigInteger\_baseSquare(), phpseclib\Math\BigInteger\_karatsubaSquare(), phpseclib\Math\BigInteger\_subtract(), and phpseclib\Math\BigInteger\VALUE.

Referenced by phpseclib\Math\BigInteger\_karatsubaSquare(), and phpseclib\Math\BigInteger\_square().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ _lshift()

phpseclib\Math\BigInteger::_lshift (   $shift)

Logical Left Shift.

Shifts BigInteger's by $shift bits.

Parameters
int$shift@access private

Definition at line 3469 of file BigInteger.php.

3470 {
3471 if ($shift == 0) {
3472 return;
3473 }
3474
3475 $num_digits = (int) ($shift / self::$base);
3476 $shift %= self::$base;
3477 $shift = 1 << $shift;
3478
3479 $carry = 0;
3480
3481 for ($i = 0; $i < count($this->value); ++$i) {
3482 $temp = $this->value[$i] * $shift + $carry;
3483 $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
3484 $this->value[$i] = (int) ($temp - $carry * self::$baseFull);
3485 }
3486
3487 if ($carry) {
3488 $this->value[count($this->value)] = $carry;
3489 }
3490
3491 while ($num_digits--) {
3492 array_unshift($this->value, 0);
3493 }
3494 }

References $base, phpseclib\Math\BigInteger\$base, and $i.

◆ _make_odd()

phpseclib\Math\BigInteger::_make_odd ( )

Make the current number odd.

If the current number is odd it'll be unchanged. If it's even, one will be added to it.

See also
self::randomPrime() @access private

Definition at line 3290 of file BigInteger.php.

3291 {
3292 switch (MATH_BIGINTEGER_MODE) {
3293 case self::MODE_GMP:
3294 gmp_setbit($this->value, 0);
3295 break;
3296 case self::MODE_BCMATH:
3297 if ($this->value[strlen($this->value) - 1] % 2 == 0) {
3298 $this->value = bcadd($this->value, '1');
3299 }
3300 break;
3301 default:
3302 $this->value[0] |= 1;
3303 }
3304 }

References phpseclib\Math\BigInteger\MODE_BCMATH, and phpseclib\Math\BigInteger\MODE_GMP.

◆ _mod2()

phpseclib\Math\BigInteger::_mod2 (   $n)

Modulos for Powers of Two.

Calculates $x$n, where $n = 2**$e, for some $e. Since this is basically the same as doing $x & ($n-1), we'll just use this function as a wrapper for doing that.

See also
self::_slidingWindow() @access private
Parameters

phpseclib\Math\BigInteger

Returns
\phpseclib\Math\BigInteger

Definition at line 1982 of file BigInteger.php.

1983 {
1984 $temp = new static();
1985 $temp->value = array(1);
1986 return $this->bitwise_and($n->subtract($temp));
1987 }
bitwise_and($x)
Logical And.

References $n, and phpseclib\Math\BigInteger\bitwise_and().

+ Here is the call graph for this function:

◆ _modInverse67108864()

phpseclib\Math\BigInteger::_modInverse67108864 (   $x)

Modular Inverse of a number mod 2**26 (eg.

67108864)

Based off of the bnpInvDigit function implemented and justified in the following URL:

http://www-cs-students.stanford.edu/~tjw/jsbn/jsbn.js

The following URL provides more info:

http://groups.google.com/group/sci.crypt/msg/7a137205c1be7d85

As for why we do all the bitmasking... strange things can happen when converting from floats to ints. For instance, on some computers, var_dump((int) -4294967297) yields int(-1) and on others, it yields int(-2147483648). To avoid problems stemming from this, we use bitmasks to guarantee that ints aren't auto-converted to floats. The outermost bitmask is present because without it, there's no guarantee that the "residue" returned would be the so-called "common residue". We use fmod, in the last step, because the maximum possible $x is 26 bits and the maximum $result is 16 bits. Thus, we have to be able to handle up to 40 bits, which only 64-bit floating points will support.

Thanks to Pedro Gimeno Fortea for input!

See also
self::_montgomery() @access private
Parameters
array$x
Returns
int

Definition at line 2399 of file BigInteger.php.

2400 {
2401 $x = -$x[0];
2402 $result = $x & 0x3; // x**-1 mod 2**2
2403 $result = ($result * (2 - $x * $result)) & 0xF; // x**-1 mod 2**4
2404 $result = ($result * (2 - ($x & 0xFF) * $result)) & 0xFF; // x**-1 mod 2**8
2405 $result = ($result * ((2 - ($x & 0xFFFF) * $result) & 0xFFFF)) & 0xFFFF; // x**-1 mod 2**16
2406 $result = fmod($result * (2 - fmod($x * $result, self::$baseFull)), self::$baseFull); // x**-1 mod 2**26
2407 return $result & self::$maxDigit;
2408 }

References phpseclib\Math\BigInteger\$maxDigit, $result, and $x.

Referenced by phpseclib\Math\BigInteger\_montgomery(), and phpseclib\Math\BigInteger\_montgomeryMultiply().

+ Here is the caller graph for this function:

◆ _montgomery()

phpseclib\Math\BigInteger::_montgomery (   $x,
  $n 
)

Montgomery Modular Reduction.

($x->_prepMontgomery($n))->_montgomery($n) yields $x % $n. MPM 6.3 provides insights on how this can be improved upon (basically, by using the comba method). gcd($n, 2) must be equal to one for this function to work correctly.

See also
self::_prepMontgomery()
self::_slidingWindow() @access private
Parameters
array$x
array$n
Returns
array

Definition at line 2263 of file BigInteger.php.

2264 {
2265 static $cache = array(
2266 self::VARIABLE => array(),
2267 self::DATA => array()
2268 );
2269
2270 if (($key = array_search($n, $cache[self::VARIABLE])) === false) {
2271 $key = count($cache[self::VARIABLE]);
2272 $cache[self::VARIABLE][] = $x;
2273 $cache[self::DATA][] = $this->_modInverse67108864($n);
2274 }
2275
2276 $k = count($n);
2277
2278 $result = array(self::VALUE => $x);
2279
2280 for ($i = 0; $i < $k; ++$i) {
2281 $temp = $result[self::VALUE][$i] * $cache[self::DATA][$key];
2282 $temp = $temp - self::$baseFull * (self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31));
2283 $temp = $this->_regularMultiply(array($temp), $n);
2284 $temp = array_merge($this->_array_repeat(0, $i), $temp);
2285 $result = $this->_add($result[self::VALUE], false, $temp, false);
2286 }
2287
2288 $result[self::VALUE] = array_slice($result[self::VALUE], $k);
2289
2290 if ($this->_compare($result, false, $n, false) >= 0) {
2291 $result = $this->_subtract($result[self::VALUE], false, $n, false);
2292 }
2293
2294 return $result[self::VALUE];
2295 }
_modInverse67108864($x)
Modular Inverse of a number mod 2**26 (eg.

References $base, $i, $key, $n, $result, $x, phpseclib\Math\BigInteger\_add(), phpseclib\Math\BigInteger\_array_repeat(), phpseclib\Math\BigInteger\_compare(), phpseclib\Math\BigInteger\_modInverse67108864(), phpseclib\Math\BigInteger\_regularMultiply(), phpseclib\Math\BigInteger\_subtract(), phpseclib\Math\BigInteger\DATA, phpseclib\Math\BigInteger\VALUE, and phpseclib\Math\BigInteger\VARIABLE.

Referenced by phpseclib\Math\BigInteger\_montgomeryMultiply(), and phpseclib\Math\BigInteger\_reduce().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ _montgomeryMultiply()

phpseclib\Math\BigInteger::_montgomeryMultiply (   $x,
  $y,
  $m 
)

Montgomery Multiply.

Interleaves the montgomery reduction and long multiplication algorithms together as described in HAC 14.36

See also
self::_prepMontgomery()
self::_montgomery() @access private
Parameters
array$x
array$y
array$m
Returns
array

Definition at line 2311 of file BigInteger.php.

2312 {
2313 $temp = $this->_multiply($x, false, $y, false);
2314 return $this->_montgomery($temp[self::VALUE], $m);
2315
2316 // the following code, although not callable, can be run independently of the above code
2317 // although the above code performed better in my benchmarks the following could might
2318 // perform better under different circumstances. in lieu of deleting it it's just been
2319 // made uncallable
2320
2321 static $cache = array(
2322 self::VARIABLE => array(),
2323 self::DATA => array()
2324 );
2325
2326 if (($key = array_search($m, $cache[self::VARIABLE])) === false) {
2327 $key = count($cache[self::VARIABLE]);
2328 $cache[self::VARIABLE][] = $m;
2329 $cache[self::DATA][] = $this->_modInverse67108864($m);
2330 }
2331
2332 $n = max(count($x), count($y), count($m));
2333 $x = array_pad($x, $n, 0);
2334 $y = array_pad($y, $n, 0);
2335 $m = array_pad($m, $n, 0);
2336 $a = array(self::VALUE => $this->_array_repeat(0, $n + 1));
2337 for ($i = 0; $i < $n; ++$i) {
2338 $temp = $a[self::VALUE][0] + $x[$i] * $y[0];
2339 $temp = $temp - self::$baseFull * (self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31));
2340 $temp = $temp * $cache[self::DATA][$key];
2341 $temp = $temp - self::$baseFull * (self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31));
2342 $temp = $this->_add($this->_regularMultiply(array($x[$i]), $y), false, $this->_regularMultiply(array($temp), $m), false);
2343 $a = $this->_add($a[self::VALUE], false, $temp[self::VALUE], false);
2344 $a[self::VALUE] = array_slice($a[self::VALUE], 1);
2345 }
2346 if ($this->_compare($a[self::VALUE], false, $m, false) >= 0) {
2347 $a = $this->_subtract($a[self::VALUE], false, $m, false);
2348 }
2349 return $a[self::VALUE];
2350 }
_montgomery($x, $n)
Montgomery Modular Reduction.
$y
Definition: example_007.php:83

References $base, $i, $key, $m, $n, $x, $y, phpseclib\Math\BigInteger\_add(), phpseclib\Math\BigInteger\_array_repeat(), phpseclib\Math\BigInteger\_compare(), phpseclib\Math\BigInteger\_modInverse67108864(), phpseclib\Math\BigInteger\_montgomery(), phpseclib\Math\BigInteger\_multiply(), phpseclib\Math\BigInteger\_regularMultiply(), phpseclib\Math\BigInteger\_subtract(), phpseclib\Math\BigInteger\DATA, phpseclib\Math\BigInteger\VALUE, and phpseclib\Math\BigInteger\VARIABLE.

Referenced by phpseclib\Math\BigInteger\_multiplyReduce(), and phpseclib\Math\BigInteger\_squareReduce().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ _multiply()

phpseclib\Math\BigInteger::_multiply (   $x_value,
  $x_negative,
  $y_value,
  $y_negative 
)

Performs multiplication.

Parameters
array$x_value
bool$x_negative
array$y_value
bool$y_negative
Returns
array @access private

Definition at line 1155 of file BigInteger.php.

1156 {
1157 //if ( $x_value == $y_value ) {
1158 // return array(
1159 // self::VALUE => $this->_square($x_value),
1160 // self::SIGN => $x_sign != $y_value
1161 // );
1162 //}
1163
1164 $x_length = count($x_value);
1165 $y_length = count($y_value);
1166
1167 if (!$x_length || !$y_length) { // a 0 is being multiplied
1168 return array(
1169 self::VALUE => array(),
1170 self::SIGN => false
1171 );
1172 }
1173
1174 return array(
1175 self::VALUE => min($x_length, $y_length) < 2 * self::KARATSUBA_CUTOFF ?
1176 $this->_trim($this->_regularMultiply($x_value, $y_value)) :
1177 $this->_trim($this->_karatsuba($x_value, $y_value)),
1178 self::SIGN => $x_negative != $y_negative
1179 );
1180 }

References phpseclib\Math\BigInteger\_karatsuba(), phpseclib\Math\BigInteger\_regularMultiply(), and phpseclib\Math\BigInteger\_trim().

Referenced by phpseclib\Math\BigInteger\_barrett(), phpseclib\Math\BigInteger\_montgomeryMultiply(), phpseclib\Math\BigInteger\_multiplyReduce(), phpseclib\Math\BigInteger\_regularBarrett(), and phpseclib\Math\BigInteger\multiply().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ _multiplyLower()

phpseclib\Math\BigInteger::_multiplyLower (   $x_value,
  $x_negative,
  $y_value,
  $y_negative,
  $stop 
)

Performs long multiplication up to $stop digits.

If you're going to be doing array_slice($product->value, 0, $stop), some cycles can be saved.

See also
self::_regularBarrett()
Parameters
array$x_value
bool$x_negative
array$y_value
bool$y_negative
int$stop
Returns
array @access private

Definition at line 2184 of file BigInteger.php.

2185 {
2186 $x_length = count($x_value);
2187 $y_length = count($y_value);
2188
2189 if (!$x_length || !$y_length) { // a 0 is being multiplied
2190 return array(
2191 self::VALUE => array(),
2192 self::SIGN => false
2193 );
2194 }
2195
2196 if ($x_length < $y_length) {
2197 $temp = $x_value;
2198 $x_value = $y_value;
2199 $y_value = $temp;
2200
2201 $x_length = count($x_value);
2202 $y_length = count($y_value);
2203 }
2204
2205 $product_value = $this->_array_repeat(0, $x_length + $y_length);
2206
2207 // the following for loop could be removed if the for loop following it
2208 // (the one with nested for loops) initially set $i to 0, but
2209 // doing so would also make the result in one set of unnecessary adds,
2210 // since on the outermost loops first pass, $product->value[$k] is going
2211 // to always be 0
2212
2213 $carry = 0;
2214
2215 for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0, $k = $i
2216 $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0
2217 $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
2218 $product_value[$j] = (int) ($temp - self::$baseFull * $carry);
2219 }
2220
2221 if ($j < $stop) {
2222 $product_value[$j] = $carry;
2223 }
2224
2225 // the above for loop is what the previous comment was talking about. the
2226 // following for loop is the "one with nested for loops"
2227
2228 for ($i = 1; $i < $y_length; ++$i) {
2229 $carry = 0;
2230
2231 for ($j = 0, $k = $i; $j < $x_length && $k < $stop; ++$j, ++$k) {
2232 $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry;
2233 $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
2234 $product_value[$k] = (int) ($temp - self::$baseFull * $carry);
2235 }
2236
2237 if ($k < $stop) {
2238 $product_value[$k] = $carry;
2239 }
2240 }
2241
2242 return array(
2243 self::VALUE => $this->_trim($product_value),
2244 self::SIGN => $x_negative != $y_negative
2245 );
2246 }

References $base, $i, phpseclib\Math\BigInteger\_array_repeat(), and phpseclib\Math\BigInteger\_trim().

Referenced by phpseclib\Math\BigInteger\_regularBarrett().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ _multiplyReduce()

phpseclib\Math\BigInteger::_multiplyReduce (   $x,
  $y,
  $n,
  $mode 
)

Modular multiply.

See also
self::_slidingWindow() @access private
Parameters
array$x
array$y
array$n
int$mode
Returns
array

Definition at line 1944 of file BigInteger.php.

1945 {
1946 if ($mode == self::MONTGOMERY) {
1947 return $this->_montgomeryMultiply($x, $y, $n);
1948 }
1949 $temp = $this->_multiply($x, false, $y, false);
1950 return $this->_reduce($temp[self::VALUE], $n, $mode);
1951 }
_montgomeryMultiply($x, $y, $m)
Montgomery Multiply.
_reduce($x, $n, $mode)
Modular reduction.

References $n, $x, $y, phpseclib\Math\BigInteger\_montgomeryMultiply(), phpseclib\Math\BigInteger\_multiply(), and phpseclib\Math\BigInteger\_reduce().

Referenced by phpseclib\Math\BigInteger\_slidingWindow().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ _normalize()

phpseclib\Math\BigInteger::_normalize (   $result)

Normalize.

Removes leading zeros and truncates (if necessary) to maintain the appropriate precision

Parameters

phpseclib\Math\BigInteger

Returns
\phpseclib\Math\BigInteger
See also
self::_trim() @access private

Definition at line 3540 of file BigInteger.php.

3541 {
3542 $result->precision = $this->precision;
3543 $result->bitmask = $this->bitmask;
3544
3545 switch (MATH_BIGINTEGER_MODE) {
3546 case self::MODE_GMP:
3547 if ($this->bitmask !== false) {
3548 $result->value = gmp_and($result->value, $result->bitmask->value);
3549 }
3550
3551 return $result;
3552 case self::MODE_BCMATH:
3553 if (!empty($result->bitmask->value)) {
3554 $result->value = bcmod($result->value, $result->bitmask->value);
3555 }
3556
3557 return $result;
3558 }
3559
3560 $value = &$result->value;
3561
3562 if (!count($value)) {
3563 return $result;
3564 }
3565
3566 $value = $this->_trim($value);
3567
3568 if (!empty($result->bitmask->value)) {
3569 $length = min(count($value), count($this->bitmask->value));
3570 $value = array_slice($value, 0, $length);
3571
3572 for ($i = 0; $i < $length; ++$i) {
3573 $value[$i] = $value[$i] & $this->bitmask->value[$i];
3574 }
3575 }
3576
3577 return $result;
3578 }
$bitmask
Precision Bitmask.
Definition: BigInteger.php:216

References phpseclib\Math\BigInteger\$bitmask, $i, phpseclib\Math\BigInteger\$precision, $result, phpseclib\Math\BigInteger\$value, phpseclib\Math\BigInteger\_trim(), phpseclib\Math\BigInteger\MODE_BCMATH, and phpseclib\Math\BigInteger\MODE_GMP.

Referenced by phpseclib\Math\BigInteger\add(), phpseclib\Math\BigInteger\bitwise_and(), phpseclib\Math\BigInteger\bitwise_leftRotate(), phpseclib\Math\BigInteger\bitwise_leftShift(), phpseclib\Math\BigInteger\bitwise_not(), phpseclib\Math\BigInteger\bitwise_or(), phpseclib\Math\BigInteger\bitwise_rightShift(), phpseclib\Math\BigInteger\bitwise_xor(), phpseclib\Math\BigInteger\divide(), phpseclib\Math\BigInteger\extendedGCD(), phpseclib\Math\BigInteger\modInverse(), phpseclib\Math\BigInteger\modPow(), phpseclib\Math\BigInteger\multiply(), phpseclib\Math\BigInteger\random(), phpseclib\Math\BigInteger\setPrecision(), and phpseclib\Math\BigInteger\subtract().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ _prepareReduce()

phpseclib\Math\BigInteger::_prepareReduce (   $x,
  $n,
  $mode 
)

Modular reduction preperation.

See also
self::_slidingWindow() @access private
Parameters
array$x
array$n
int$mode
Returns
array

Definition at line 1925 of file BigInteger.php.

1926 {
1927 if ($mode == self::MONTGOMERY) {
1928 return $this->_prepMontgomery($x, $n);
1929 }
1930 return $this->_reduce($x, $n, $mode);
1931 }
_prepMontgomery($x, $n)
Prepare a number for use in Montgomery Modular Reductions.

References $n, $x, phpseclib\Math\BigInteger\_prepMontgomery(), and phpseclib\Math\BigInteger\_reduce().

Referenced by phpseclib\Math\BigInteger\_slidingWindow().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ _prepMontgomery()

phpseclib\Math\BigInteger::_prepMontgomery (   $x,
  $n 
)

Prepare a number for use in Montgomery Modular Reductions.

See also
self::_montgomery()
self::_slidingWindow() @access private
Parameters
array$x
array$n
Returns
array

Definition at line 2362 of file BigInteger.php.

2363 {
2364 $lhs = new static();
2365 $lhs->value = array_merge($this->_array_repeat(0, count($n)), $x);
2366 $rhs = new static();
2367 $rhs->value = $n;
2368
2369 list(, $temp) = $lhs->divide($rhs);
2370 return $temp->value;
2371 }

References $n, $x, and phpseclib\Math\BigInteger\_array_repeat().

Referenced by phpseclib\Math\BigInteger\_prepareReduce().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ _random_number_helper()

phpseclib\Math\BigInteger::_random_number_helper (   $size)

Generates a random BigInteger.

Byte length is equal to $length. Uses \phpseclib\Crypt\Random if it's loaded and mt_rand if it's not.

Parameters
int$length
Returns
\phpseclib\Math\BigInteger @access private

Definition at line 3072 of file BigInteger.php.

3073 {
3074 if (class_exists('\phpseclib\Crypt\Random')) {
3075 $random = Random::string($size);
3076 } else {
3077 $random = '';
3078
3079 if ($size & 1) {
3080 $random.= chr(mt_rand(0, 255));
3081 }
3082
3083 $blocks = $size >> 1;
3084 for ($i = 0; $i < $blocks; ++$i) {
3085 // mt_rand(-2147483648, 0x7FFFFFFF) always produces -2147483648 on some systems
3086 $random.= pack('n', mt_rand(0, 0xFFFF));
3087 }
3088 }
3089
3090 return new static($random, 256);
3091 }
static string($length)
Generate a random string.
Definition: Random.php:54

References $i, $size, and phpseclib\Crypt\Random\string().

Referenced by phpseclib\Math\BigInteger\random().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ _reduce()

phpseclib\Math\BigInteger::_reduce (   $x,
  $n,
  $mode 
)

Modular reduction.

For most $modes this will return the remainder.

See also
self::_slidingWindow() @access private
Parameters
array$x
array$n
int$mode
Returns
array

Definition at line 1888 of file BigInteger.php.

1889 {
1890 switch ($mode) {
1891 case self::MONTGOMERY:
1892 return $this->_montgomery($x, $n);
1893 case self::BARRETT:
1894 return $this->_barrett($x, $n);
1895 case self::POWEROF2:
1896 $lhs = new static();
1897 $lhs->value = $x;
1898 $rhs = new static();
1899 $rhs->value = $n;
1900 return $x->_mod2($n);
1901 case self::CLASSIC:
1902 $lhs = new static();
1903 $lhs->value = $x;
1904 $rhs = new static();
1905 $rhs->value = $n;
1906 list(, $temp) = $lhs->divide($rhs);
1907 return $temp->value;
1908 case self::NONE:
1909 return $x;
1910 default:
1911 // an invalid $mode was provided
1912 }
1913 }
const MONTGOMERY
#+ Reduction constants
Definition: BigInteger.php:75
_barrett($n, $m)
Barrett Modular Reduction.

References $n, $x, phpseclib\Math\BigInteger\_barrett(), phpseclib\Math\BigInteger\_montgomery(), phpseclib\Math\BigInteger\BARRETT, phpseclib\Math\BigInteger\CLASSIC, phpseclib\Math\BigInteger\MONTGOMERY, phpseclib\Math\BigInteger\NONE, and phpseclib\Math\BigInteger\POWEROF2.

Referenced by phpseclib\Math\BigInteger\_multiplyReduce(), phpseclib\Math\BigInteger\_prepareReduce(), phpseclib\Math\BigInteger\_slidingWindow(), and phpseclib\Math\BigInteger\_squareReduce().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ _regularBarrett()

phpseclib\Math\BigInteger::_regularBarrett (   $x,
  $n 
)

(Regular) Barrett Modular Reduction

For numbers with more than four digits BigInteger::_barrett() is faster. The difference between that and this is that this function does not fold the denominator into a smaller form.

See also
self::_slidingWindow() @access private
Parameters
array$x
array$n
Returns
array

Definition at line 2110 of file BigInteger.php.

2111 {
2112 static $cache = array(
2113 self::VARIABLE => array(),
2114 self::DATA => array()
2115 );
2116
2117 $n_length = count($n);
2118
2119 if (count($x) > 2 * $n_length) {
2120 $lhs = new static();
2121 $rhs = new static();
2122 $lhs->value = $x;
2123 $rhs->value = $n;
2124 list(, $temp) = $lhs->divide($rhs);
2125 return $temp->value;
2126 }
2127
2128 if (($key = array_search($n, $cache[self::VARIABLE])) === false) {
2129 $key = count($cache[self::VARIABLE]);
2130 $cache[self::VARIABLE][] = $n;
2131 $lhs = new static();
2132 $lhs_value = &$lhs->value;
2133 $lhs_value = $this->_array_repeat(0, 2 * $n_length);
2134 $lhs_value[] = 1;
2135 $rhs = new static();
2136 $rhs->value = $n;
2137 list($temp, ) = $lhs->divide($rhs); // m.length
2138 $cache[self::DATA][] = $temp->value;
2139 }
2140
2141 // 2 * m.length - (m.length - 1) = m.length + 1
2142 $temp = array_slice($x, $n_length - 1);
2143 // (m.length + 1) + m.length = 2 * m.length + 1
2144 $temp = $this->_multiply($temp, false, $cache[self::DATA][$key], false);
2145 // (2 * m.length + 1) - (m.length - 1) = m.length + 2
2146 $temp = array_slice($temp[self::VALUE], $n_length + 1);
2147
2148 // m.length + 1
2149 $result = array_slice($x, 0, $n_length + 1);
2150 // m.length + 1
2151 $temp = $this->_multiplyLower($temp, false, $n, false, $n_length + 1);
2152 // $temp == array_slice($temp->_multiply($temp, false, $n, false)->value, 0, $n_length + 1)
2153
2154 if ($this->_compare($result, false, $temp[self::VALUE], $temp[self::SIGN]) < 0) {
2155 $corrector_value = $this->_array_repeat(0, $n_length + 1);
2156 $corrector_value[count($corrector_value)] = 1;
2157 $result = $this->_add($result, false, $corrector_value, false);
2159 }
2160
2161 // at this point, we're subtracting a number with m.length + 1 digits from another number with m.length + 1 digits
2162 $result = $this->_subtract($result, false, $temp[self::VALUE], $temp[self::SIGN]);
2163 while ($this->_compare($result[self::VALUE], $result[self::SIGN], $n, false) > 0) {
2164 $result = $this->_subtract($result[self::VALUE], $result[self::SIGN], $n, false);
2165 }
2166
2167 return $result[self::VALUE];
2168 }
_multiplyLower($x_value, $x_negative, $y_value, $y_negative, $stop)
Performs long multiplication up to $stop digits.

References $key, $n, $result, $x, phpseclib\Math\BigInteger\_add(), phpseclib\Math\BigInteger\_array_repeat(), phpseclib\Math\BigInteger\_compare(), phpseclib\Math\BigInteger\_multiply(), phpseclib\Math\BigInteger\_multiplyLower(), phpseclib\Math\BigInteger\_subtract(), phpseclib\Math\BigInteger\DATA, phpseclib\Math\BigInteger\VALUE, and phpseclib\Math\BigInteger\VARIABLE.

Referenced by phpseclib\Math\BigInteger\_barrett().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ _regularMultiply()

phpseclib\Math\BigInteger::_regularMultiply (   $x_value,
  $y_value 
)

Performs long multiplication on two BigIntegers.

Modeled after 'multiply' in MutableBigInteger.java.

Parameters
array$x_value
array$y_value
Returns
array @access private

Definition at line 1192 of file BigInteger.php.

1193 {
1194 $x_length = count($x_value);
1195 $y_length = count($y_value);
1196
1197 if (!$x_length || !$y_length) { // a 0 is being multiplied
1198 return array();
1199 }
1200
1201 if ($x_length < $y_length) {
1202 $temp = $x_value;
1203 $x_value = $y_value;
1204 $y_value = $temp;
1205
1206 $x_length = count($x_value);
1207 $y_length = count($y_value);
1208 }
1209
1210 $product_value = $this->_array_repeat(0, $x_length + $y_length);
1211
1212 // the following for loop could be removed if the for loop following it
1213 // (the one with nested for loops) initially set $i to 0, but
1214 // doing so would also make the result in one set of unnecessary adds,
1215 // since on the outermost loops first pass, $product->value[$k] is going
1216 // to always be 0
1217
1218 $carry = 0;
1219
1220 for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0
1221 $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0
1222 $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
1223 $product_value[$j] = (int) ($temp - self::$baseFull * $carry);
1224 }
1225
1226 $product_value[$j] = $carry;
1227
1228 // the above for loop is what the previous comment was talking about. the
1229 // following for loop is the "one with nested for loops"
1230 for ($i = 1; $i < $y_length; ++$i) {
1231 $carry = 0;
1232
1233 for ($j = 0, $k = $i; $j < $x_length; ++$j, ++$k) {
1234 $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry;
1235 $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
1236 $product_value[$k] = (int) ($temp - self::$baseFull * $carry);
1237 }
1238
1239 $product_value[$k] = $carry;
1240 }
1241
1242 return $product_value;
1243 }

References $base, $i, and phpseclib\Math\BigInteger\_array_repeat().

Referenced by phpseclib\Math\BigInteger\_karatsuba(), phpseclib\Math\BigInteger\_montgomery(), phpseclib\Math\BigInteger\_montgomeryMultiply(), and phpseclib\Math\BigInteger\_multiply().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ _rshift()

phpseclib\Math\BigInteger::_rshift (   $shift)

Logical Right Shift.

Shifts BigInteger's by $shift bits.

Parameters
int$shift@access private

Definition at line 3504 of file BigInteger.php.

3505 {
3506 if ($shift == 0) {
3507 return;
3508 }
3509
3510 $num_digits = (int) ($shift / self::$base);
3511 $shift %= self::$base;
3512 $carry_shift = self::$base - $shift;
3513 $carry_mask = (1 << $shift) - 1;
3514
3515 if ($num_digits) {
3516 $this->value = array_slice($this->value, $num_digits);
3517 }
3518
3519 $carry = 0;
3520
3521 for ($i = count($this->value) - 1; $i >= 0; --$i) {
3522 $temp = $this->value[$i] >> $shift | $carry;
3523 $carry = ($this->value[$i] & $carry_mask) << $carry_shift;
3524 $this->value[$i] = $temp;
3525 }
3526
3527 $this->value = $this->_trim($this->value);
3528 }

References $base, phpseclib\Math\BigInteger\$base, $i, and phpseclib\Math\BigInteger\_trim().

+ Here is the call graph for this function:

◆ _safe_divide()

phpseclib\Math\BigInteger::_safe_divide (   $x,
  $y 
)

Single digit division.

Even if int64 is being used the division operator will return a float64 value if the dividend is not evenly divisible by the divisor. Since a float64 doesn't have the precision of int64 this is a problem so, when int64 is being used, we'll guarantee that the dividend is divisible by first subtracting the remainder.

@access private

Parameters
int$x
int$y
Returns
int

Definition at line 3745 of file BigInteger.php.

3746 {
3747 if (self::$base === 26) {
3748 return (int) ($x / $y);
3749 }
3750
3751 // self::$base === 31
3752 return ($x - ($x % $y)) / $y;
3753 }

References $base, $x, and $y.

Referenced by phpseclib\Math\BigInteger\_divide_digit(), and phpseclib\Math\BigInteger\divide().

+ Here is the caller graph for this function:

◆ _slidingWindow()

phpseclib\Math\BigInteger::_slidingWindow (   $e,
  $n,
  $mode 
)

Sliding Window k-ary Modular Exponentiation.

Based on HAC 14.85 / MPM 7.7. In a departure from those algorithims, however, this function performs a modular reduction after every multiplication and squaring operation. As such, this function has the same preconditions that the reductions being used do.

Parameters
\phpseclib\Math\BigInteger$e
\phpseclib\Math\BigInteger$n
int$mode
Returns
\phpseclib\Math\BigInteger @access private

Definition at line 1811 of file BigInteger.php.

1812 {
1813 static $window_ranges = array(7, 25, 81, 241, 673, 1793); // from BigInteger.java's oddModPow function
1814 //static $window_ranges = array(0, 7, 36, 140, 450, 1303, 3529); // from MPM 7.3.1
1815
1816 $e_value = $e->value;
1817 $e_length = count($e_value) - 1;
1818 $e_bits = decbin($e_value[$e_length]);
1819 for ($i = $e_length - 1; $i >= 0; --$i) {
1820 $e_bits.= str_pad(decbin($e_value[$i]), self::$base, '0', STR_PAD_LEFT);
1821 }
1822
1823 $e_length = strlen($e_bits);
1824
1825 // calculate the appropriate window size.
1826 // $window_size == 3 if $window_ranges is between 25 and 81, for example.
1827 for ($i = 0, $window_size = 1; $e_length > $window_ranges[$i] && $i < count($window_ranges); ++$window_size, ++$i) {
1828 }
1829
1830 $n_value = $n->value;
1831
1832 // precompute $this^0 through $this^$window_size
1833 $powers = array();
1834 $powers[1] = $this->_prepareReduce($this->value, $n_value, $mode);
1835 $powers[2] = $this->_squareReduce($powers[1], $n_value, $mode);
1836
1837 // we do every other number since substr($e_bits, $i, $j+1) (see below) is supposed to end
1838 // in a 1. ie. it's supposed to be odd.
1839 $temp = 1 << ($window_size - 1);
1840 for ($i = 1; $i < $temp; ++$i) {
1841 $i2 = $i << 1;
1842 $powers[$i2 + 1] = $this->_multiplyReduce($powers[$i2 - 1], $powers[2], $n_value, $mode);
1843 }
1844
1845 $result = array(1);
1846 $result = $this->_prepareReduce($result, $n_value, $mode);
1847
1848 for ($i = 0; $i < $e_length;) {
1849 if (!$e_bits[$i]) {
1850 $result = $this->_squareReduce($result, $n_value, $mode);
1851 ++$i;
1852 } else {
1853 for ($j = $window_size - 1; $j > 0; --$j) {
1854 if (!empty($e_bits[$i + $j])) {
1855 break;
1856 }
1857 }
1858
1859 // eg. the length of substr($e_bits, $i, $j + 1)
1860 for ($k = 0; $k <= $j; ++$k) {
1861 $result = $this->_squareReduce($result, $n_value, $mode);
1862 }
1863
1864 $result = $this->_multiplyReduce($result, $powers[bindec(substr($e_bits, $i, $j + 1))], $n_value, $mode);
1865
1866 $i += $j + 1;
1867 }
1868 }
1869
1870 $temp = new static();
1871 $temp->value = $this->_reduce($result, $n_value, $mode);
1872
1873 return $temp;
1874 }
_prepareReduce($x, $n, $mode)
Modular reduction preperation.
_squareReduce($x, $n, $mode)
Modular square.
_multiplyReduce($x, $y, $n, $mode)
Modular multiply.

References $base, $i, $n, $result, phpseclib\Math\BigInteger\_multiplyReduce(), phpseclib\Math\BigInteger\_prepareReduce(), phpseclib\Math\BigInteger\_reduce(), and phpseclib\Math\BigInteger\_squareReduce().

Referenced by phpseclib\Math\BigInteger\modPow().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ _square()

phpseclib\Math\BigInteger::_square (   $x = false)

Performs squaring.

Parameters
array$x
Returns
array @access private

Definition at line 1294 of file BigInteger.php.

1295 {
1296 return count($x) < 2 * self::KARATSUBA_CUTOFF ?
1297 $this->_trim($this->_baseSquare($x)) :
1298 $this->_trim($this->_karatsubaSquare($x));
1299 }

References $x, phpseclib\Math\BigInteger\_baseSquare(), phpseclib\Math\BigInteger\_karatsubaSquare(), and phpseclib\Math\BigInteger\_trim().

Referenced by phpseclib\Math\BigInteger\_squareReduce(), and phpseclib\Math\BigInteger\modPow().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ _squareReduce()

phpseclib\Math\BigInteger::_squareReduce (   $x,
  $n,
  $mode 
)

Modular square.

See also
self::_slidingWindow() @access private
Parameters
array$x
array$n
int$mode
Returns
array

Definition at line 1963 of file BigInteger.php.

1964 {
1965 if ($mode == self::MONTGOMERY) {
1966 return $this->_montgomeryMultiply($x, $x, $n);
1967 }
1968 return $this->_reduce($this->_square($x), $n, $mode);
1969 }
_square($x=false)
Performs squaring.

References $n, $x, phpseclib\Math\BigInteger\_montgomeryMultiply(), phpseclib\Math\BigInteger\_reduce(), and phpseclib\Math\BigInteger\_square().

Referenced by phpseclib\Math\BigInteger\_slidingWindow().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ _subtract()

phpseclib\Math\BigInteger::_subtract (   $x_value,
  $x_negative,
  $y_value,
  $y_negative 
)

Performs subtraction.

Parameters
array$x_value
bool$x_negative
array$y_value
bool$y_negative
Returns
array @access private

Definition at line 1022 of file BigInteger.php.

1023 {
1024 $x_size = count($x_value);
1025 $y_size = count($y_value);
1026
1027 if ($x_size == 0) {
1028 return array(
1029 self::VALUE => $y_value,
1030 self::SIGN => !$y_negative
1031 );
1032 } elseif ($y_size == 0) {
1033 return array(
1034 self::VALUE => $x_value,
1035 self::SIGN => $x_negative
1036 );
1037 }
1038
1039 // add, if appropriate (ie. -$x - +$y or +$x - -$y)
1040 if ($x_negative != $y_negative) {
1041 $temp = $this->_add($x_value, false, $y_value, false);
1042 $temp[self::SIGN] = $x_negative;
1043
1044 return $temp;
1045 }
1046
1047 $diff = $this->_compare($x_value, $x_negative, $y_value, $y_negative);
1048
1049 if (!$diff) {
1050 return array(
1051 self::VALUE => array(),
1052 self::SIGN => false
1053 );
1054 }
1055
1056 // switch $x and $y around, if appropriate.
1057 if ((!$x_negative && $diff < 0) || ($x_negative && $diff > 0)) {
1058 $temp = $x_value;
1059 $x_value = $y_value;
1060 $y_value = $temp;
1061
1062 $x_negative = !$x_negative;
1063
1064 $x_size = count($x_value);
1065 $y_size = count($y_value);
1066 }
1067
1068 // at this point, $x_value should be at least as big as - if not bigger than - $y_value
1069
1070 $carry = 0;
1071 for ($i = 0, $j = 1; $j < $y_size; $i+=2, $j+=2) {
1072 $sum = $x_value[$j] * self::$baseFull + $x_value[$i] - $y_value[$j] * self::$baseFull - $y_value[$i] - $carry;
1073 $carry = $sum < 0; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1
1074 $sum = $carry ? $sum + self::$maxDigit2 : $sum;
1075
1076 $temp = self::$base === 26 ? intval($sum / 0x4000000) : ($sum >> 31);
1077
1078 $x_value[$i] = (int) ($sum - self::$baseFull * $temp);
1079 $x_value[$j] = $temp;
1080 }
1081
1082 if ($j == $y_size) { // ie. if $y_size is odd
1083 $sum = $x_value[$i] - $y_value[$i] - $carry;
1084 $carry = $sum < 0;
1085 $x_value[$i] = $carry ? $sum + self::$baseFull : $sum;
1086 ++$i;
1087 }
1088
1089 if ($carry) {
1090 for (; !$x_value[$i]; ++$i) {
1091 $x_value[$i] = self::$maxDigit;
1092 }
1093 --$x_value[$i];
1094 }
1095
1096 return array(
1097 self::VALUE => $this->_trim($x_value),
1098 self::SIGN => $x_negative
1099 );
1100 }

References $base, phpseclib\Math\BigInteger\$baseFull, $i, phpseclib\Math\BigInteger\$maxDigit, phpseclib\Math\BigInteger\$maxDigit2, phpseclib\Math\BigInteger\_add(), phpseclib\Math\BigInteger\_compare(), phpseclib\Math\BigInteger\_trim(), and phpseclib\Math\BigInteger\SIGN.

Referenced by phpseclib\Math\BigInteger\_add(), phpseclib\Math\BigInteger\_barrett(), phpseclib\Math\BigInteger\_karatsuba(), phpseclib\Math\BigInteger\_karatsubaSquare(), phpseclib\Math\BigInteger\_montgomery(), phpseclib\Math\BigInteger\_montgomeryMultiply(), phpseclib\Math\BigInteger\_regularBarrett(), and phpseclib\Math\BigInteger\subtract().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ _trim()

phpseclib\Math\BigInteger::_trim (   $value)

Trim.

Removes leading zeros

Parameters
array$value
Returns
\phpseclib\Math\BigInteger @access private

Definition at line 3589 of file BigInteger.php.

3590 {
3591 for ($i = count($value) - 1; $i >= 0; --$i) {
3592 if ($value[$i]) {
3593 break;
3594 }
3595 unset($value[$i]);
3596 }
3597
3598 return $value;
3599 }

References $i, and phpseclib\Math\BigInteger\$value.

Referenced by phpseclib\Math\BigInteger\_add(), phpseclib\Math\BigInteger\_barrett(), phpseclib\Math\BigInteger\_multiply(), phpseclib\Math\BigInteger\_multiplyLower(), phpseclib\Math\BigInteger\_normalize(), phpseclib\Math\BigInteger\_rshift(), phpseclib\Math\BigInteger\_square(), and phpseclib\Math\BigInteger\_subtract().

+ Here is the caller graph for this function:

◆ abs()

phpseclib\Math\BigInteger::abs ( )

Absolute value.

Returns
\phpseclib\Math\BigInteger @access public

Definition at line 2642 of file BigInteger.php.

2643 {
2644 $temp = new static();
2645
2646 switch (MATH_BIGINTEGER_MODE) {
2647 case self::MODE_GMP:
2648 $temp->value = gmp_abs($this->value);
2649 break;
2650 case self::MODE_BCMATH:
2651 $temp->value = (bccomp($this->value, '0', 0) < 0) ? substr($this->value, 1) : $this->value;
2652 break;
2653 default:
2654 $temp->value = $this->value;
2655 }
2656
2657 return $temp;
2658 }

References phpseclib\Math\BigInteger\$value, phpseclib\Math\BigInteger\MODE_BCMATH, and phpseclib\Math\BigInteger\MODE_GMP.

Referenced by phpseclib\Math\BigInteger\__construct(), and phpseclib\Math\BigInteger\modInverse().

+ Here is the caller graph for this function:

◆ add()

phpseclib\Math\BigInteger::add (   $y)

Adds two BigIntegers.

Here's an example: <?php $a = new \phpseclib\Math\BigInteger('10'); $b = new \phpseclib\Math\BigInteger('20');

$c = $a->add($b);

echo $c->toString(); // outputs 30 ?>

Parameters
\phpseclib\Math\BigInteger$y
Returns
\phpseclib\Math\BigInteger @access public

Definition at line 859 of file BigInteger.php.

860 {
861 switch (MATH_BIGINTEGER_MODE) {
862 case self::MODE_GMP:
863 $temp = new static();
864 $temp->value = gmp_add($this->value, $y->value);
865
866 return $this->_normalize($temp);
868 $temp = new static();
869 $temp->value = bcadd($this->value, $y->value, 0);
870
871 return $this->_normalize($temp);
872 }
873
874 $temp = $this->_add($this->value, $this->is_negative, $y->value, $y->is_negative);
875
876 $result = new static();
877 $result->value = $temp[self::VALUE];
878 $result->is_negative = $temp[self::SIGN];
879
880 return $this->_normalize($result);
881 }
_normalize($result)
Normalize.

References $result, $y, phpseclib\Math\BigInteger\_add(), phpseclib\Math\BigInteger\_normalize(), phpseclib\Math\BigInteger\MODE_BCMATH, phpseclib\Math\BigInteger\MODE_GMP, phpseclib\Math\BigInteger\SIGN, and phpseclib\Math\BigInteger\VALUE.

Referenced by phpseclib\Math\BigInteger\__construct(), and phpseclib\Math\BigInteger\toBytes().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ bitwise_and()

phpseclib\Math\BigInteger::bitwise_and (   $x)

Logical And.

Parameters
\phpseclib\Math\BigInteger$x@access public

Definition at line 2776 of file BigInteger.php.

2777 {
2778 switch (MATH_BIGINTEGER_MODE) {
2779 case self::MODE_GMP:
2780 $temp = new static();
2781 $temp->value = gmp_and($this->value, $x->value);
2782
2783 return $this->_normalize($temp);
2784 case self::MODE_BCMATH:
2785 $left = $this->toBytes();
2786 $right = $x->toBytes();
2787
2788 $length = max(strlen($left), strlen($right));
2789
2790 $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
2791 $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
2792
2793 return $this->_normalize(new static($left & $right, 256));
2794 }
2795
2796 $result = $this->copy();
2797
2798 $length = min(count($x->value), count($this->value));
2799
2800 $result->value = array_slice($result->value, 0, $length);
2801
2802 for ($i = 0; $i < $length; ++$i) {
2803 $result->value[$i]&= $x->value[$i];
2804 }
2805
2806 return $this->_normalize($result);
2807 }
toBytes($twos_compliment=false)
Converts a BigInteger to a byte string (eg.
Definition: BigInteger.php:522

References $i, $result, $x, phpseclib\Math\BigInteger\_normalize(), phpseclib\Math\BigInteger\copy(), phpseclib\Math\BigInteger\MODE_BCMATH, phpseclib\Math\BigInteger\MODE_GMP, and phpseclib\Math\BigInteger\toBytes().

Referenced by phpseclib\Math\BigInteger\_mod2().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ bitwise_leftRotate()

phpseclib\Math\BigInteger::bitwise_leftRotate (   $shift)

Logical Left Rotate.

Instead of the top x bits being dropped they're appended to the shifted bit string.

Parameters
int$shift
Returns
\phpseclib\Math\BigInteger @access public

Definition at line 3013 of file BigInteger.php.

3014 {
3015 $bits = $this->toBytes();
3016
3017 if ($this->precision > 0) {
3019 if (MATH_BIGINTEGER_MODE == self::MODE_BCMATH) {
3020 $mask = $this->bitmask->subtract(new static(1));
3021 $mask = $mask->toBytes();
3022 } else {
3023 $mask = $this->bitmask->toBytes();
3024 }
3025 } else {
3026 $temp = ord($bits[0]);
3027 for ($i = 0; $temp >> $i; ++$i) {
3028 }
3029 $precision = 8 * strlen($bits) - 8 + $i;
3030 $mask = chr((1 << ($precision & 0x7)) - 1) . str_repeat(chr(0xFF), $precision >> 3);
3031 }
3032
3033 if ($shift < 0) {
3034 $shift+= $precision;
3035 }
3036 $shift%= $precision;
3037
3038 if (!$shift) {
3039 return $this->copy();
3040 }
3041
3042 $left = $this->bitwise_leftShift($shift);
3043 $left = $left->bitwise_and(new static($mask, 256));
3044 $right = $this->bitwise_rightShift($precision - $shift);
3045 $result = MATH_BIGINTEGER_MODE != self::MODE_BCMATH ? $left->bitwise_or($right) : $left->add($right);
3046 return $this->_normalize($result);
3047 }
bitwise_rightShift($shift)
Logical Right Shift.
bitwise_leftShift($shift)
Logical Left Shift.
$mask
Definition: example_042.php:90

References $i, $mask, phpseclib\Math\BigInteger\$precision, $result, phpseclib\Math\BigInteger\_normalize(), phpseclib\Math\BigInteger\bitwise_leftShift(), phpseclib\Math\BigInteger\bitwise_rightShift(), phpseclib\Math\BigInteger\copy(), and phpseclib\Math\BigInteger\toBytes().

Referenced by phpseclib\Math\BigInteger\bitwise_rightRotate().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ bitwise_leftShift()

phpseclib\Math\BigInteger::bitwise_leftShift (   $shift)

Logical Left Shift.

Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift.

Parameters
int$shift
Returns
\phpseclib\Math\BigInteger @access public

Definition at line 2976 of file BigInteger.php.

2977 {
2978 $temp = new static();
2979
2980 switch (MATH_BIGINTEGER_MODE) {
2981 case self::MODE_GMP:
2982 static $two;
2983
2984 if (!isset($two)) {
2985 $two = gmp_init('2');
2986 }
2987
2988 $temp->value = gmp_mul($this->value, gmp_pow($two, $shift));
2989
2990 break;
2991 case self::MODE_BCMATH:
2992 $temp->value = bcmul($this->value, bcpow('2', $shift, 0), 0);
2993
2994 break;
2995 default: // could just replace _rshift with this, but then all _lshift() calls would need to be rewritten
2996 // and I don't want to do that...
2997 $temp->value = $this->value;
2998 $temp->_lshift($shift);
2999 }
3000
3001 return $this->_normalize($temp);
3002 }

References phpseclib\Math\BigInteger\$value, phpseclib\Math\BigInteger\_normalize(), phpseclib\Math\BigInteger\MODE_BCMATH, and phpseclib\Math\BigInteger\MODE_GMP.

Referenced by phpseclib\Math\BigInteger\bitwise_leftRotate().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ bitwise_not()

phpseclib\Math\BigInteger::bitwise_not ( )

Logical Not.

@access public

Definition at line 2896 of file BigInteger.php.

2897 {
2898 // calculuate "not" without regard to $this->precision
2899 // (will always result in a smaller number. ie. ~1 isn't 1111 1110 - it's 0)
2900 $temp = $this->toBytes();
2901 if ($temp == '') {
2902 return '';
2903 }
2904 $pre_msb = decbin(ord($temp[0]));
2905 $temp = ~$temp;
2906 $msb = decbin(ord($temp[0]));
2907 if (strlen($msb) == 8) {
2908 $msb = substr($msb, strpos($msb, '0'));
2909 }
2910 $temp[0] = chr(bindec($msb));
2911
2912 // see if we need to add extra leading 1's
2913 $current_bits = strlen($pre_msb) + 8 * strlen($temp) - 8;
2914 $new_bits = $this->precision - $current_bits;
2915 if ($new_bits <= 0) {
2916 return $this->_normalize(new static($temp, 256));
2917 }
2918
2919 // generate as many leading 1's as we need to.
2920 $leading_ones = chr((1 << ($new_bits & 0x7)) - 1) . str_repeat(chr(0xFF), $new_bits >> 3);
2921 $this->_base256_lshift($leading_ones, $current_bits);
2922
2923 $temp = str_pad($temp, strlen($leading_ones), chr(0), STR_PAD_LEFT);
2924
2925 return $this->_normalize(new static($leading_ones | $temp, 256));
2926 }
_base256_lshift(&$x, $shift)
Logical Left Shift.

References phpseclib\Math\BigInteger\$msb, phpseclib\Math\BigInteger\_base256_lshift(), phpseclib\Math\BigInteger\_normalize(), and phpseclib\Math\BigInteger\toBytes().

+ Here is the call graph for this function:

◆ bitwise_or()

phpseclib\Math\BigInteger::bitwise_or (   $x)

Logical Or.

Parameters
\phpseclib\Math\BigInteger$x@access public

Definition at line 2817 of file BigInteger.php.

2818 {
2819 switch (MATH_BIGINTEGER_MODE) {
2820 case self::MODE_GMP:
2821 $temp = new static();
2822 $temp->value = gmp_or($this->value, $x->value);
2823
2824 return $this->_normalize($temp);
2825 case self::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 static($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 }

References $i, $result, $x, phpseclib\Math\BigInteger\_normalize(), phpseclib\Math\BigInteger\copy(), phpseclib\Math\BigInteger\MODE_BCMATH, phpseclib\Math\BigInteger\MODE_GMP, and phpseclib\Math\BigInteger\toBytes().

+ Here is the call graph for this function:

◆ bitwise_rightRotate()

phpseclib\Math\BigInteger::bitwise_rightRotate (   $shift)

Logical Right Rotate.

Instead of the bottom x bits being dropped they're prepended to the shifted bit string.

Parameters
int$shift
Returns
\phpseclib\Math\BigInteger @access public

Definition at line 3058 of file BigInteger.php.

3059 {
3060 return $this->bitwise_leftRotate(-$shift);
3061 }
bitwise_leftRotate($shift)
Logical Left Rotate.

References phpseclib\Math\BigInteger\bitwise_leftRotate().

+ Here is the call graph for this function:

◆ bitwise_rightShift()

phpseclib\Math\BigInteger::bitwise_rightShift (   $shift)

Logical Right Shift.

Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift.

Parameters
int$shift
Returns
\phpseclib\Math\BigInteger @access public

Definition at line 2938 of file BigInteger.php.

2939 {
2940 $temp = new static();
2941
2942 switch (MATH_BIGINTEGER_MODE) {
2943 case self::MODE_GMP:
2944 static $two;
2945
2946 if (!isset($two)) {
2947 $two = gmp_init('2');
2948 }
2949
2950 $temp->value = gmp_div_q($this->value, gmp_pow($two, $shift));
2951
2952 break;
2953 case self::MODE_BCMATH:
2954 $temp->value = bcdiv($this->value, bcpow('2', $shift, 0), 0);
2955
2956 break;
2957 default: // could just replace _lshift with this, but then all _lshift() calls would need to be rewritten
2958 // and I don't want to do that...
2959 $temp->value = $this->value;
2960 $temp->_rshift($shift);
2961 }
2962
2963 return $this->_normalize($temp);
2964 }

References phpseclib\Math\BigInteger\$value, phpseclib\Math\BigInteger\_normalize(), phpseclib\Math\BigInteger\MODE_BCMATH, and phpseclib\Math\BigInteger\MODE_GMP.

Referenced by phpseclib\Math\BigInteger\bitwise_leftRotate().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ bitwise_xor()

phpseclib\Math\BigInteger::bitwise_xor (   $x)

Logical Exclusive-Or.

Parameters
\phpseclib\Math\BigInteger$x@access public

Definition at line 2857 of file BigInteger.php.

2858 {
2859 switch (MATH_BIGINTEGER_MODE) {
2860 case self::MODE_GMP:
2861 $temp = new static();
2862 $temp->value = gmp_xor($this->value, $x->value);
2863
2864 return $this->_normalize($temp);
2865 case self::MODE_BCMATH:
2866 $left = $this->toBytes();
2867 $right = $x->toBytes();
2868
2869 $length = max(strlen($left), strlen($right));
2870
2871 $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
2872 $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
2873
2874 return $this->_normalize(new static($left ^ $right, 256));
2875 }
2876
2877 $length = max(count($this->value), count($x->value));
2878 $result = $this->copy();
2879 $result->value = array_pad($result->value, $length, 0);
2880 $x->value = array_pad($x->value, $length, 0);
2881
2882 for ($i = 0; $i < $length; ++$i) {
2883 $result->value[$i]^= $x->value[$i];
2884 }
2885
2886 return $this->_normalize($result);
2887 }

References $i, $result, $x, phpseclib\Math\BigInteger\_normalize(), phpseclib\Math\BigInteger\copy(), phpseclib\Math\BigInteger\MODE_BCMATH, phpseclib\Math\BigInteger\MODE_GMP, and phpseclib\Math\BigInteger\toBytes().

+ Here is the call graph for this function:

◆ compare()

phpseclib\Math\BigInteger::compare (   $y)

Compares two numbers.

Although one might think !$x->compare($y) means $x != $y, it, in fact, means the opposite. The reason for this is demonstrated thusly:

$x > $y: $x->compare($y) > 0 $x < $y: $x->compare($y) < 0 $x == $y: $x->compare($y) == 0

Note how the same comparison operator is used. If you want to test for equality, use $x->equals($y).

Parameters
\phpseclib\Math\BigInteger$y
Returns
int < 0 if $this is less than $y; > 0 if $this is greater than $y, and 0 if they are equal. @access public
See also
self::equals()

Definition at line 2678 of file BigInteger.php.

2679 {
2680 switch (MATH_BIGINTEGER_MODE) {
2681 case self::MODE_GMP:
2682 return gmp_cmp($this->value, $y->value);
2683 case self::MODE_BCMATH:
2684 return bccomp($this->value, $y->value, 0);
2685 }
2686
2687 return $this->_compare($this->value, $this->is_negative, $y->value, $y->is_negative);
2688 }

References $y, phpseclib\Math\BigInteger\_compare(), phpseclib\Math\BigInteger\MODE_BCMATH, and phpseclib\Math\BigInteger\MODE_GMP.

Referenced by phpseclib\Math\BigInteger\modInverse(), phpseclib\Math\BigInteger\modPow(), phpseclib\Math\BigInteger\toBits(), and phpseclib\Math\BigInteger\toBytes().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ copy()

phpseclib\Math\BigInteger::copy ( )

Copy an object.

PHP5 passes objects by reference while PHP4 passes by value. As such, we need a function to guarantee that all objects are passed by value, when appropriate. More information can be found here:

http://php.net/language.oop5.basic#51624

@access public

See also
self::__clone()
Returns
\phpseclib\Math\BigInteger

Definition at line 728 of file BigInteger.php.

729 {
730 $temp = new static();
731 $temp->value = $this->value;
732 $temp->is_negative = $this->is_negative;
733 $temp->precision = $this->precision;
734 $temp->bitmask = $this->bitmask;
735 return $temp;
736 }

References phpseclib\Math\BigInteger\$bitmask, phpseclib\Math\BigInteger\$is_negative, phpseclib\Math\BigInteger\$precision, and phpseclib\Math\BigInteger\$value.

Referenced by phpseclib\Math\BigInteger\__clone(), phpseclib\Math\BigInteger\bitwise_and(), phpseclib\Math\BigInteger\bitwise_leftRotate(), phpseclib\Math\BigInteger\bitwise_or(), phpseclib\Math\BigInteger\bitwise_xor(), phpseclib\Math\BigInteger\divide(), phpseclib\Math\BigInteger\extendedGCD(), phpseclib\Math\BigInteger\isPrime(), phpseclib\Math\BigInteger\toBytes(), and phpseclib\Math\BigInteger\toString().

+ Here is the caller graph for this function:

◆ divide()

phpseclib\Math\BigInteger::divide (   $y)

Divides two BigIntegers.

Returns an array whose first element contains the quotient and whose second element contains the "common residue". If the remainder would be positive, the "common residue" and the remainder are the same. If the remainder would be negative, the "common residue" is equal to the sum of the remainder and the divisor (basically, the "common residue" is the first positive modulo).

Here's an example: <?php $a = new \phpseclib\Math\BigInteger('10'); $b = new \phpseclib\Math\BigInteger('20');

list($quotient, $remainder) = $a->divide($b);

echo $quotient->toString(); // outputs 0 echo "\r\n"; echo $remainder->toString(); // outputs 10 ?>

Parameters
\phpseclib\Math\BigInteger$y
Returns
array @access public

Definition at line 1406 of file BigInteger.php.

1407 {
1408 switch (MATH_BIGINTEGER_MODE) {
1409 case self::MODE_GMP:
1410 $quotient = new static();
1411 $remainder = new static();
1412
1413 list($quotient->value, $remainder->value) = gmp_div_qr($this->value, $y->value);
1414
1415 if (gmp_sign($remainder->value) < 0) {
1416 $remainder->value = gmp_add($remainder->value, gmp_abs($y->value));
1417 }
1418
1419 return array($this->_normalize($quotient), $this->_normalize($remainder));
1420 case self::MODE_BCMATH:
1421 $quotient = new static();
1422 $remainder = new static();
1423
1424 $quotient->value = bcdiv($this->value, $y->value, 0);
1425 $remainder->value = bcmod($this->value, $y->value);
1426
1427 if ($remainder->value[0] == '-') {
1428 $remainder->value = bcadd($remainder->value, $y->value[0] == '-' ? substr($y->value, 1) : $y->value, 0);
1429 }
1430
1431 return array($this->_normalize($quotient), $this->_normalize($remainder));
1432 }
1433
1434 if (count($y->value) == 1) {
1435 list($q, $r) = $this->_divide_digit($this->value, $y->value[0]);
1436 $quotient = new static();
1437 $remainder = new static();
1438 $quotient->value = $q;
1439 $remainder->value = array($r);
1440 $quotient->is_negative = $this->is_negative != $y->is_negative;
1441 return array($this->_normalize($quotient), $this->_normalize($remainder));
1442 }
1443
1444 static $zero;
1445 if (!isset($zero)) {
1446 $zero = new static();
1447 }
1448
1449 $x = $this->copy();
1450 $y = $y->copy();
1451
1452 $x_sign = $x->is_negative;
1453 $y_sign = $y->is_negative;
1454
1455 $x->is_negative = $y->is_negative = false;
1456
1457 $diff = $x->compare($y);
1458
1459 if (!$diff) {
1460 $temp = new static();
1461 $temp->value = array(1);
1462 $temp->is_negative = $x_sign != $y_sign;
1463 return array($this->_normalize($temp), $this->_normalize(new static()));
1464 }
1465
1466 if ($diff < 0) {
1467 // if $x is negative, "add" $y.
1468 if ($x_sign) {
1469 $x = $y->subtract($x);
1470 }
1471 return array($this->_normalize(new static()), $this->_normalize($x));
1472 }
1473
1474 // normalize $x and $y as described in HAC 14.23 / 14.24
1475 $msb = $y->value[count($y->value) - 1];
1476 for ($shift = 0; !($msb & self::$msb); ++$shift) {
1477 $msb <<= 1;
1478 }
1479 $x->_lshift($shift);
1480 $y->_lshift($shift);
1481 $y_value = &$y->value;
1482
1483 $x_max = count($x->value) - 1;
1484 $y_max = count($y->value) - 1;
1485
1486 $quotient = new static();
1487 $quotient_value = &$quotient->value;
1488 $quotient_value = $this->_array_repeat(0, $x_max - $y_max + 1);
1489
1490 static $temp, $lhs, $rhs;
1491 if (!isset($temp)) {
1492 $temp = new static();
1493 $lhs = new static();
1494 $rhs = new static();
1495 }
1496 $temp_value = &$temp->value;
1497 $rhs_value = &$rhs->value;
1498
1499 // $temp = $y << ($x_max - $y_max-1) in base 2**26
1500 $temp_value = array_merge($this->_array_repeat(0, $x_max - $y_max), $y_value);
1501
1502 while ($x->compare($temp) >= 0) {
1503 // calculate the "common residue"
1504 ++$quotient_value[$x_max - $y_max];
1505 $x = $x->subtract($temp);
1506 $x_max = count($x->value) - 1;
1507 }
1508
1509 for ($i = $x_max; $i >= $y_max + 1; --$i) {
1510 $x_value = &$x->value;
1511 $x_window = array(
1512 isset($x_value[$i]) ? $x_value[$i] : 0,
1513 isset($x_value[$i - 1]) ? $x_value[$i - 1] : 0,
1514 isset($x_value[$i - 2]) ? $x_value[$i - 2] : 0
1515 );
1516 $y_window = array(
1517 $y_value[$y_max],
1518 ($y_max > 0) ? $y_value[$y_max - 1] : 0
1519 );
1520
1521 $q_index = $i - $y_max - 1;
1522 if ($x_window[0] == $y_window[0]) {
1523 $quotient_value[$q_index] = self::$maxDigit;
1524 } else {
1525 $quotient_value[$q_index] = $this->_safe_divide(
1526 $x_window[0] * self::$baseFull + $x_window[1],
1527 $y_window[0]
1528 );
1529 }
1530
1531 $temp_value = array($y_window[1], $y_window[0]);
1532
1533 $lhs->value = array($quotient_value[$q_index]);
1534 $lhs = $lhs->multiply($temp);
1535
1536 $rhs_value = array($x_window[2], $x_window[1], $x_window[0]);
1537
1538 while ($lhs->compare($rhs) > 0) {
1539 --$quotient_value[$q_index];
1540
1541 $lhs->value = array($quotient_value[$q_index]);
1542 $lhs = $lhs->multiply($temp);
1543 }
1544
1545 $adjust = $this->_array_repeat(0, $q_index);
1546 $temp_value = array($quotient_value[$q_index]);
1547 $temp = $temp->multiply($y);
1548 $temp_value = &$temp->value;
1549 $temp_value = array_merge($adjust, $temp_value);
1550
1551 $x = $x->subtract($temp);
1552
1553 if ($x->compare($zero) < 0) {
1554 $temp_value = array_merge($adjust, $y_value);
1555 $x = $x->add($temp);
1556
1557 --$quotient_value[$q_index];
1558 }
1559
1560 $x_max = count($x_value) - 1;
1561 }
1562
1563 // unnormalize the remainder
1564 $x->_rshift($shift);
1565
1566 $quotient->is_negative = $x_sign != $y_sign;
1567
1568 // calculate the "common residue", if appropriate
1569 if ($x_sign) {
1570 $y->_rshift($shift);
1571 $x = $y->subtract($x);
1572 }
1573
1574 return array($this->_normalize($quotient), $this->_normalize($x));
1575 }
_divide_digit($dividend, $divisor)
Divides a BigInteger by a regular integer.
$r
Definition: example_031.php:79

References $i, phpseclib\Math\BigInteger\$maxDigit, phpseclib\Math\BigInteger\$msb, $r, $x, $y, phpseclib\Math\BigInteger\_array_repeat(), phpseclib\Math\BigInteger\_divide_digit(), phpseclib\Math\BigInteger\_normalize(), phpseclib\Math\BigInteger\_safe_divide(), phpseclib\Math\BigInteger\copy(), phpseclib\Math\BigInteger\MODE_BCMATH, and phpseclib\Math\BigInteger\MODE_GMP.

Referenced by phpseclib\Math\BigInteger\isPrime(), and phpseclib\Math\BigInteger\modPow().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ equals()

phpseclib\Math\BigInteger::equals (   $x)

Tests the equality of two numbers.

If you need to see if one number is greater than or less than another number, use BigInteger::compare()

Parameters
\phpseclib\Math\BigInteger$x
Returns
bool @access public
See also
self::compare()

Definition at line 2736 of file BigInteger.php.

2737 {
2738 switch (MATH_BIGINTEGER_MODE) {
2739 case self::MODE_GMP:
2740 return gmp_cmp($this->value, $x->value) == 0;
2741 default:
2742 return $this->value === $x->value && $this->is_negative == $x->is_negative;
2743 }
2744 }

References $x, and phpseclib\Math\BigInteger\MODE_GMP.

Referenced by phpseclib\Math\BigInteger\isPrime().

+ Here is the caller graph for this function:

◆ extendedGCD()

phpseclib\Math\BigInteger::extendedGCD (   $n)

Calculates the greatest common divisor and Bezout's identity.

Say you have 693 and 609. The GCD is 21. Bezout's identity states that there exist integers x and y such that 693*x + 609*y == 21. In point of fact, there are actually an infinite number of x and y combinations and which combination is returned is dependant upon which mode is in use. See Bezout's identity - Wikipedia for more information.

Here's an example: <?php $a = new \phpseclib\Math\BigInteger(693); $b = new \phpseclib\Math\BigInteger(609);

extract($a->extendedGCD($b));

echo $gcd->toString() . "\r\n"; // outputs 21 echo $a->toString() * $x->toString() + $b->toString() * $y->toString(); // outputs 21 ?>

Parameters
\phpseclib\Math\BigInteger$n
Returns
\phpseclib\Math\BigInteger @access public

Definition at line 2501 of file BigInteger.php.

2502 {
2503 switch (MATH_BIGINTEGER_MODE) {
2504 case self::MODE_GMP:
2505 extract(gmp_gcdext($this->value, $n->value));
2506
2507 return array(
2508 'gcd' => $this->_normalize(new static($g)),
2509 'x' => $this->_normalize(new static($s)),
2510 'y' => $this->_normalize(new static($t))
2511 );
2512 case self::MODE_BCMATH:
2513 // it might be faster to use the binary xGCD algorithim here, as well, but (1) that algorithim works
2514 // best when the base is a power of 2 and (2) i don't think it'd make much difference, anyway. as is,
2515 // the basic extended euclidean algorithim is what we're using.
2516
2517 $u = $this->value;
2518 $v = $n->value;
2519
2520 $a = '1';
2521 $b = '0';
2522 $c = '0';
2523 $d = '1';
2524
2525 while (bccomp($v, '0', 0) != 0) {
2526 $q = bcdiv($u, $v, 0);
2527
2528 $temp = $u;
2529 $u = $v;
2530 $v = bcsub($temp, bcmul($v, $q, 0), 0);
2531
2532 $temp = $a;
2533 $a = $c;
2534 $c = bcsub($temp, bcmul($a, $q, 0), 0);
2535
2536 $temp = $b;
2537 $b = $d;
2538 $d = bcsub($temp, bcmul($b, $q, 0), 0);
2539 }
2540
2541 return array(
2542 'gcd' => $this->_normalize(new static($u)),
2543 'x' => $this->_normalize(new static($a)),
2544 'y' => $this->_normalize(new static($b))
2545 );
2546 }
2547
2548 $y = $n->copy();
2549 $x = $this->copy();
2550 $g = new static();
2551 $g->value = array(1);
2552
2553 while (!(($x->value[0] & 1)|| ($y->value[0] & 1))) {
2554 $x->_rshift(1);
2555 $y->_rshift(1);
2556 $g->_lshift(1);
2557 }
2558
2559 $u = $x->copy();
2560 $v = $y->copy();
2561
2562 $a = new static();
2563 $b = new static();
2564 $c = new static();
2565 $d = new static();
2566
2567 $a->value = $d->value = $g->value = array(1);
2568 $b->value = $c->value = array();
2569
2570 while (!empty($u->value)) {
2571 while (!($u->value[0] & 1)) {
2572 $u->_rshift(1);
2573 if ((!empty($a->value) && ($a->value[0] & 1)) || (!empty($b->value) && ($b->value[0] & 1))) {
2574 $a = $a->add($y);
2575 $b = $b->subtract($x);
2576 }
2577 $a->_rshift(1);
2578 $b->_rshift(1);
2579 }
2580
2581 while (!($v->value[0] & 1)) {
2582 $v->_rshift(1);
2583 if ((!empty($d->value) && ($d->value[0] & 1)) || (!empty($c->value) && ($c->value[0] & 1))) {
2584 $c = $c->add($y);
2585 $d = $d->subtract($x);
2586 }
2587 $c->_rshift(1);
2588 $d->_rshift(1);
2589 }
2590
2591 if ($u->compare($v) >= 0) {
2592 $u = $u->subtract($v);
2593 $a = $a->subtract($c);
2594 $b = $b->subtract($d);
2595 } else {
2596 $v = $v->subtract($u);
2597 $c = $c->subtract($a);
2598 $d = $d->subtract($b);
2599 }
2600 }
2601
2602 return array(
2603 'gcd' => $this->_normalize($g->multiply($v)),
2604 'x' => $this->_normalize($c),
2605 'y' => $this->_normalize($d)
2606 );
2607 }
for( $i=6;$i< 13;$i++) for($i=1; $i< 13; $i++) $d
Definition: date.php:296
$s
Definition: pwgen.php:45

References $c, $d, $n, $s, $t, phpseclib\Math\BigInteger\$value, $x, $y, phpseclib\Math\BigInteger\_normalize(), phpseclib\Math\BigInteger\copy(), phpseclib\Math\BigInteger\MODE_BCMATH, and phpseclib\Math\BigInteger\MODE_GMP.

Referenced by phpseclib\Math\BigInteger\gcd(), and phpseclib\Math\BigInteger\modInverse().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ gcd()

phpseclib\Math\BigInteger::gcd (   $n)

Calculates the greatest common divisor.

Say you have 693 and 609. The GCD is 21.

Here's an example: <?php $a = new \phpseclib\Math\BigInteger(693); $b = new \phpseclib\Math\BigInteger(609);

$gcd = a->extendedGCD($b);

echo $gcd->toString() . "\r\n"; // outputs 21 ?>

Parameters
\phpseclib\Math\BigInteger$n
Returns
\phpseclib\Math\BigInteger @access public

Definition at line 2630 of file BigInteger.php.

2631 {
2632 extract($this->extendedGCD($n));
2633 return $gcd;
2634 }
extendedGCD($n)
Calculates the greatest common divisor and Bezout's identity.

References $n, and phpseclib\Math\BigInteger\extendedGCD().

+ Here is the call graph for this function:

◆ isPrime()

phpseclib\Math\BigInteger::isPrime (   $t = false)

Checks a numer to see if it's prime.

Assuming the $t parameter is not set, this function has an error rate of 2**-80. The main motivation for the $t parameter is distributability. BigInteger::randomPrime() can be distributed across multiple pageloads on a website instead of just one.

Parameters
\phpseclib\Math\BigInteger$t
Returns
bool @access public

Definition at line 3320 of file BigInteger.php.

3321 {
3322 $length = strlen($this->toBytes());
3323
3324 if (!$t) {
3325 // see HAC 4.49 "Note (controlling the error probability)"
3326 // @codingStandardsIgnoreStart
3327 if ($length >= 163) { $t = 2; } // floor(1300 / 8)
3328 else if ($length >= 106) { $t = 3; } // floor( 850 / 8)
3329 else if ($length >= 81 ) { $t = 4; } // floor( 650 / 8)
3330 else if ($length >= 68 ) { $t = 5; } // floor( 550 / 8)
3331 else if ($length >= 56 ) { $t = 6; } // floor( 450 / 8)
3332 else if ($length >= 50 ) { $t = 7; } // floor( 400 / 8)
3333 else if ($length >= 43 ) { $t = 8; } // floor( 350 / 8)
3334 else if ($length >= 37 ) { $t = 9; } // floor( 300 / 8)
3335 else if ($length >= 31 ) { $t = 12; } // floor( 250 / 8)
3336 else if ($length >= 25 ) { $t = 15; } // floor( 200 / 8)
3337 else if ($length >= 18 ) { $t = 18; } // floor( 150 / 8)
3338 else { $t = 27; }
3339 // @codingStandardsIgnoreEnd
3340 }
3341
3342 // ie. gmp_testbit($this, 0)
3343 // ie. isEven() or !isOdd()
3344 switch (MATH_BIGINTEGER_MODE) {
3345 case self::MODE_GMP:
3346 return gmp_prob_prime($this->value, $t) != 0;
3347 case self::MODE_BCMATH:
3348 if ($this->value === '2') {
3349 return true;
3350 }
3351 if ($this->value[strlen($this->value) - 1] % 2 == 0) {
3352 return false;
3353 }
3354 break;
3355 default:
3356 if ($this->value == array(2)) {
3357 return true;
3358 }
3359 if (~$this->value[0] & 1) {
3360 return false;
3361 }
3362 }
3363
3364 static $primes, $zero, $one, $two;
3365
3366 if (!isset($primes)) {
3367 $primes = array(
3368 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
3369 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137,
3370 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227,
3371 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313,
3372 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419,
3373 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509,
3374 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617,
3375 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727,
3376 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829,
3377 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947,
3378 953, 967, 971, 977, 983, 991, 997
3379 );
3380
3381 if (MATH_BIGINTEGER_MODE != self::MODE_INTERNAL) {
3382 for ($i = 0; $i < count($primes); ++$i) {
3383 $primes[$i] = new static($primes[$i]);
3384 }
3385 }
3386
3387 $zero = new static();
3388 $one = new static(1);
3389 $two = new static(2);
3390 }
3391
3392 if ($this->equals($one)) {
3393 return false;
3394 }
3395
3396 // see HAC 4.4.1 "Random search for probable primes"
3397 if (MATH_BIGINTEGER_MODE != self::MODE_INTERNAL) {
3398 foreach ($primes as $prime) {
3399 list(, $r) = $this->divide($prime);
3400 if ($r->equals($zero)) {
3401 return $this->equals($prime);
3402 }
3403 }
3404 } else {
3406 foreach ($primes as $prime) {
3407 list(, $r) = $this->_divide_digit($value, $prime);
3408 if (!$r) {
3409 return count($value) == 1 && $value[0] == $prime;
3410 }
3411 }
3412 }
3413
3414 $n = $this->copy();
3415 $n_1 = $n->subtract($one);
3416 $n_2 = $n->subtract($two);
3417
3418 $r = $n_1->copy();
3419 $r_value = $r->value;
3420 // ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s));
3421 if (MATH_BIGINTEGER_MODE == self::MODE_BCMATH) {
3422 $s = 0;
3423 // if $n was 1, $r would be 0 and this would be an infinite loop, hence our $this->equals($one) check earlier
3424 while ($r->value[strlen($r->value) - 1] % 2 == 0) {
3425 $r->value = bcdiv($r->value, '2', 0);
3426 ++$s;
3427 }
3428 } else {
3429 for ($i = 0, $r_length = count($r_value); $i < $r_length; ++$i) {
3430 $temp = ~$r_value[$i] & 0xFFFFFF;
3431 for ($j = 1; ($temp >> $j) & 1; ++$j) {
3432 }
3433 if ($j != 25) {
3434 break;
3435 }
3436 }
3437 $s = 26 * $i + $j - 1;
3438 $r->_rshift($s);
3439 }
3440
3441 for ($i = 0; $i < $t; ++$i) {
3442 $a = $this->random($two, $n_2);
3443 $y = $a->modPow($r, $n);
3444
3445 if (!$y->equals($one) && !$y->equals($n_1)) {
3446 for ($j = 1; $j < $s && !$y->equals($n_1); ++$j) {
3447 $y = $y->modPow($two, $n);
3448 if ($y->equals($one)) {
3449 return false;
3450 }
3451 }
3452
3453 if (!$y->equals($n_1)) {
3454 return false;
3455 }
3456 }
3457 }
3458 return true;
3459 }
divide($y)
Divides two BigIntegers.
equals($x)
Tests the equality of two numbers.
random($arg1, $arg2=false)
Generate a random number.

References $i, $n, $r, $s, $t, phpseclib\Math\BigInteger\$value, $y, phpseclib\Math\BigInteger\_divide_digit(), phpseclib\Math\BigInteger\copy(), phpseclib\Math\BigInteger\divide(), phpseclib\Math\BigInteger\equals(), phpseclib\Math\BigInteger\MODE_BCMATH, phpseclib\Math\BigInteger\MODE_GMP, phpseclib\Math\BigInteger\random(), and phpseclib\Math\BigInteger\toBytes().

+ Here is the call graph for this function:

◆ modInverse()

phpseclib\Math\BigInteger::modInverse (   $n)

Calculates modular inverses.

Say you have (30 mod 17 * x mod 17) mod 17 == 1. x can be found using modular inverses.

Here's an example: <?php $a = new \phpseclib\Math\BigInteger(30); $b = new \phpseclib\Math\BigInteger(17);

$c = $a->modInverse($b); echo $c->toString(); // outputs 4

echo "\r\n";

$d = $a->multiply($c); list(, $d) = $d->divide($b); echo $d; // outputs 1 (as per the definition of modular inverse) ?>

Parameters
\phpseclib\Math\BigInteger$n
Returns
\phpseclib\Math\BigInteger|false @access public

Definition at line 2437 of file BigInteger.php.

2438 {
2439 switch (MATH_BIGINTEGER_MODE) {
2440 case self::MODE_GMP:
2441 $temp = new static();
2442 $temp->value = gmp_invert($this->value, $n->value);
2443
2444 return ($temp->value === false) ? false : $this->_normalize($temp);
2445 }
2446
2447 static $zero, $one;
2448 if (!isset($zero)) {
2449 $zero = new static();
2450 $one = new static(1);
2451 }
2452
2453 // $x mod -$n == $x mod $n.
2454 $n = $n->abs();
2455
2456 if ($this->compare($zero) < 0) {
2457 $temp = $this->abs();
2458 $temp = $temp->modInverse($n);
2459 return $this->_normalize($n->subtract($temp));
2460 }
2461
2462 extract($this->extendedGCD($n));
2463
2464 if (!$gcd->equals($one)) {
2465 return false;
2466 }
2467
2468 $x = $x->compare($zero) < 0 ? $x->add($n) : $x;
2469
2470 return $this->compare($zero) < 0 ? $this->_normalize($n->subtract($x)) : $this->_normalize($x);
2471 }
compare($y)
Compares two numbers.

References $n, $x, phpseclib\Math\BigInteger\_normalize(), phpseclib\Math\BigInteger\abs(), phpseclib\Math\BigInteger\compare(), phpseclib\Math\BigInteger\extendedGCD(), and phpseclib\Math\BigInteger\MODE_GMP.

Referenced by phpseclib\Math\BigInteger\modPow().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ modPow()

phpseclib\Math\BigInteger::modPow (   $e,
  $n 
)

Performs modular exponentiation.

Here's an example: <?php $a = new \phpseclib\Math\BigInteger('10'); $b = new \phpseclib\Math\BigInteger('20'); $c = new \phpseclib\Math\BigInteger('30');

$c = $a->modPow($b, $c);

echo $c->toString(); // outputs 10 ?>

Parameters
\phpseclib\Math\BigInteger$e
\phpseclib\Math\BigInteger$n
Returns
\phpseclib\Math\BigInteger @access public

Definition at line 1641 of file BigInteger.php.

1642 {
1643 $n = $this->bitmask !== false && $this->bitmask->compare($n) < 0 ? $this->bitmask : $n->abs();
1644
1645 if ($e->compare(new static()) < 0) {
1646 $e = $e->abs();
1647
1648 $temp = $this->modInverse($n);
1649 if ($temp === false) {
1650 return false;
1651 }
1652
1653 return $this->_normalize($temp->modPow($e, $n));
1654 }
1655
1656 if (MATH_BIGINTEGER_MODE == self::MODE_GMP) {
1657 $temp = new static();
1658 $temp->value = gmp_powm($this->value, $e->value, $n->value);
1659
1660 return $this->_normalize($temp);
1661 }
1662
1663 if ($this->compare(new static()) < 0 || $this->compare($n) > 0) {
1664 list(, $temp) = $this->divide($n);
1665 return $temp->modPow($e, $n);
1666 }
1667
1668 if (defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
1669 $components = array(
1670 'modulus' => $n->toBytes(true),
1671 'publicExponent' => $e->toBytes(true)
1672 );
1673
1674 $components = array(
1675 'modulus' => pack('Ca*a*', 2, $this->_encodeASN1Length(strlen($components['modulus'])), $components['modulus']),
1676 'publicExponent' => pack('Ca*a*', 2, $this->_encodeASN1Length(strlen($components['publicExponent'])), $components['publicExponent'])
1677 );
1678
1679 $RSAPublicKey = pack(
1680 'Ca*a*a*',
1681 48,
1682 $this->_encodeASN1Length(strlen($components['modulus']) + strlen($components['publicExponent'])),
1683 $components['modulus'],
1684 $components['publicExponent']
1685 );
1686
1687 $rsaOID = pack('H*', '300d06092a864886f70d0101010500'); // hex version of MA0GCSqGSIb3DQEBAQUA
1688 $RSAPublicKey = chr(0) . $RSAPublicKey;
1689 $RSAPublicKey = chr(3) . $this->_encodeASN1Length(strlen($RSAPublicKey)) . $RSAPublicKey;
1690
1691 $encapsulated = pack(
1692 'Ca*a*',
1693 48,
1694 $this->_encodeASN1Length(strlen($rsaOID . $RSAPublicKey)),
1695 $rsaOID . $RSAPublicKey
1696 );
1697
1698 $RSAPublicKey = "-----BEGIN PUBLIC KEY-----\r\n" .
1699 chunk_split(base64_encode($encapsulated)) .
1700 '-----END PUBLIC KEY-----';
1701
1702 $plaintext = str_pad($this->toBytes(), strlen($n->toBytes(true)) - 1, "\0", STR_PAD_LEFT);
1703
1704 if (openssl_public_encrypt($plaintext, $result, $RSAPublicKey, OPENSSL_NO_PADDING)) {
1705 return new static($result, 256);
1706 }
1707 }
1708
1709 if (MATH_BIGINTEGER_MODE == self::MODE_BCMATH) {
1710 $temp = new static();
1711 $temp->value = bcpowmod($this->value, $e->value, $n->value, 0);
1712
1713 return $this->_normalize($temp);
1714 }
1715
1716 if (empty($e->value)) {
1717 $temp = new static();
1718 $temp->value = array(1);
1719 return $this->_normalize($temp);
1720 }
1721
1722 if ($e->value == array(1)) {
1723 list(, $temp) = $this->divide($n);
1724 return $this->_normalize($temp);
1725 }
1726
1727 if ($e->value == array(2)) {
1728 $temp = new static();
1729 $temp->value = $this->_square($this->value);
1730 list(, $temp) = $temp->divide($n);
1731 return $this->_normalize($temp);
1732 }
1733
1734 return $this->_normalize($this->_slidingWindow($e, $n, self::BARRETT));
1735
1736 // the following code, although not callable, can be run independently of the above code
1737 // although the above code performed better in my benchmarks the following could might
1738 // perform better under different circumstances. in lieu of deleting it it's just been
1739 // made uncallable
1740
1741 // is the modulo odd?
1742 if ($n->value[0] & 1) {
1743 return $this->_normalize($this->_slidingWindow($e, $n, self::MONTGOMERY));
1744 }
1745 // if it's not, it's even
1746
1747 // find the lowest set bit (eg. the max pow of 2 that divides $n)
1748 for ($i = 0; $i < count($n->value); ++$i) {
1749 if ($n->value[$i]) {
1750 $temp = decbin($n->value[$i]);
1751 $j = strlen($temp) - strrpos($temp, '1') - 1;
1752 $j+= 26 * $i;
1753 break;
1754 }
1755 }
1756 // at this point, 2^$j * $n/(2^$j) == $n
1757
1758 $mod1 = $n->copy();
1759 $mod1->_rshift($j);
1760 $mod2 = new static();
1761 $mod2->value = array(1);
1762 $mod2->_lshift($j);
1763
1764 $part1 = ($mod1->value != array(1)) ? $this->_slidingWindow($e, $mod1, self::MONTGOMERY) : new static();
1765 $part2 = $this->_slidingWindow($e, $mod2, self::POWEROF2);
1766
1767 $y1 = $mod2->modInverse($mod1);
1768 $y2 = $mod1->modInverse($mod2);
1769
1770 $result = $part1->multiply($mod2);
1771 $result = $result->multiply($y1);
1772
1773 $temp = $part2->multiply($mod1);
1774 $temp = $temp->multiply($y2);
1775
1776 $result = $result->add($temp);
1777 list(, $result) = $result->divide($n);
1778
1779 return $this->_normalize($result);
1780 }
_slidingWindow($e, $n, $mode)
Sliding Window k-ary Modular Exponentiation.
modInverse($n)
Calculates modular inverses.
_encodeASN1Length($length)
DER-encode an integer.

References $i, $n, $result, phpseclib\Math\BigInteger\_encodeASN1Length(), phpseclib\Math\BigInteger\_normalize(), phpseclib\Math\BigInteger\_slidingWindow(), phpseclib\Math\BigInteger\_square(), phpseclib\Math\BigInteger\compare(), phpseclib\Math\BigInteger\divide(), phpseclib\Math\BigInteger\modInverse(), and phpseclib\Math\BigInteger\toBytes().

Referenced by phpseclib\Math\BigInteger\powMod().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ multiply()

phpseclib\Math\BigInteger::multiply (   $x)

Multiplies two BigIntegers.

Here's an example: <?php $a = new \phpseclib\Math\BigInteger('10'); $b = new \phpseclib\Math\BigInteger('20');

$c = $a->multiply($b);

echo $c->toString(); // outputs 200 ?>

Parameters
\phpseclib\Math\BigInteger$x
Returns
\phpseclib\Math\BigInteger @access public

Definition at line 1121 of file BigInteger.php.

1122 {
1123 switch (MATH_BIGINTEGER_MODE) {
1124 case self::MODE_GMP:
1125 $temp = new static();
1126 $temp->value = gmp_mul($this->value, $x->value);
1127
1128 return $this->_normalize($temp);
1129 case self::MODE_BCMATH:
1130 $temp = new static();
1131 $temp->value = bcmul($this->value, $x->value, 0);
1132
1133 return $this->_normalize($temp);
1134 }
1135
1136 $temp = $this->_multiply($this->value, $this->is_negative, $x->value, $x->is_negative);
1137
1138 $product = new static();
1139 $product->value = $temp[self::VALUE];
1140 $product->is_negative = $temp[self::SIGN];
1141
1142 return $this->_normalize($product);
1143 }

References $x, phpseclib\Math\BigInteger\_multiply(), phpseclib\Math\BigInteger\_normalize(), phpseclib\Math\BigInteger\MODE_BCMATH, phpseclib\Math\BigInteger\MODE_GMP, phpseclib\Math\BigInteger\SIGN, and phpseclib\Math\BigInteger\VALUE.

+ Here is the call graph for this function:

◆ powMod()

phpseclib\Math\BigInteger::powMod (   $e,
  $n 
)

Performs modular exponentiation.

Alias for modPow().

Parameters
\phpseclib\Math\BigInteger$e
\phpseclib\Math\BigInteger$n
Returns
\phpseclib\Math\BigInteger @access public

Definition at line 1792 of file BigInteger.php.

1793 {
1794 return $this->modPow($e, $n);
1795 }
modPow($e, $n)
Performs modular exponentiation.

References $n, and phpseclib\Math\BigInteger\modPow().

+ Here is the call graph for this function:

◆ random()

phpseclib\Math\BigInteger::random (   $arg1,
  $arg2 = false 
)

Generate a random number.

Returns a random number between $min and $max where $min and $max can be defined using one of the two methods:

$min->random($max) $max->random($min)

Parameters
\phpseclib\Math\BigInteger$arg1
\phpseclib\Math\BigInteger$arg2
Returns
\phpseclib\Math\BigInteger @access public

Definition at line 3109 of file BigInteger.php.

3110 {
3111 if ($arg1 === false) {
3112 return false;
3113 }
3114
3115 if ($arg2 === false) {
3116 $max = $arg1;
3117 $min = $this;
3118 } else {
3119 $min = $arg1;
3120 $max = $arg2;
3121 }
3122
3123 $compare = $max->compare($min);
3124
3125 if (!$compare) {
3126 return $this->_normalize($min);
3127 } elseif ($compare < 0) {
3128 // if $min is bigger then $max, swap $min and $max
3129 $temp = $max;
3130 $max = $min;
3131 $min = $temp;
3132 }
3133
3134 static $one;
3135 if (!isset($one)) {
3136 $one = new static(1);
3137 }
3138
3139 $max = $max->subtract($min->subtract($one));
3140 $size = strlen(ltrim($max->toBytes(), chr(0)));
3141
3142 /*
3143 doing $random % $max doesn't work because some numbers will be more likely to occur than others.
3144 eg. if $max is 140 and $random's max is 255 then that'd mean both $random = 5 and $random = 145
3145 would produce 5 whereas the only value of random that could produce 139 would be 139. ie.
3146 not all numbers would be equally likely. some would be more likely than others.
3147
3148 creating a whole new random number until you find one that is within the range doesn't work
3149 because, for sufficiently small ranges, the likelihood that you'd get a number within that range
3150 would be pretty small. eg. with $random's max being 255 and if your $max being 1 the probability
3151 would be pretty high that $random would be greater than $max.
3152
3153 phpseclib works around this using the technique described here:
3154
3155 http://crypto.stackexchange.com/questions/5708/creating-a-small-number-from-a-cryptographically-secure-random-string
3156 */
3157 $random_max = new static(chr(1) . str_repeat("\0", $size), 256);
3158 $random = $this->_random_number_helper($size);
3159
3160 list($max_multiple) = $random_max->divide($max);
3161 $max_multiple = $max_multiple->multiply($max);
3162
3163 while ($random->compare($max_multiple) >= 0) {
3164 $random = $random->subtract($max_multiple);
3165 $random_max = $random_max->subtract($max_multiple);
3166 $random = $random->bitwise_leftShift(8);
3167 $random = $random->add($this->_random_number_helper(1));
3168 $random_max = $random_max->bitwise_leftShift(8);
3169 list($max_multiple) = $random_max->divide($max);
3170 $max_multiple = $max_multiple->multiply($max);
3171 }
3172 list(, $random) = $random->divide($max);
3173
3174 return $this->_normalize($random->add($min));
3175 }
_random_number_helper($size)
Generates a random BigInteger.

References $size, phpseclib\Math\BigInteger\_normalize(), and phpseclib\Math\BigInteger\_random_number_helper().

Referenced by phpseclib\Math\BigInteger\isPrime(), and phpseclib\Math\BigInteger\randomPrime().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ randomPrime()

phpseclib\Math\BigInteger::randomPrime (   $arg1,
  $arg2 = false,
  $timeout = false 
)

Generate a random prime number.

If there's not a prime within the given range, false will be returned. If more than $timeout seconds have elapsed, give up and return false.

Parameters
\phpseclib\Math\BigInteger$arg1
\phpseclib\Math\BigInteger$arg2
int$timeout
Returns
Math_BigInteger|false @access public

Definition at line 3190 of file BigInteger.php.

3191 {
3192 if ($arg1 === false) {
3193 return false;
3194 }
3195
3196 if ($arg2 === false) {
3197 $max = $arg1;
3198 $min = $this;
3199 } else {
3200 $min = $arg1;
3201 $max = $arg2;
3202 }
3203
3204 $compare = $max->compare($min);
3205
3206 if (!$compare) {
3207 return $min->isPrime() ? $min : false;
3208 } elseif ($compare < 0) {
3209 // if $min is bigger then $max, swap $min and $max
3210 $temp = $max;
3211 $max = $min;
3212 $min = $temp;
3213 }
3214
3215 static $one, $two;
3216 if (!isset($one)) {
3217 $one = new static(1);
3218 $two = new static(2);
3219 }
3220
3221 $start = time();
3222
3223 $x = $this->random($min, $max);
3224
3225 // gmp_nextprime() requires PHP 5 >= 5.2.0 per <http://php.net/gmp-nextprime>.
3226 if (MATH_BIGINTEGER_MODE == self::MODE_GMP && extension_loaded('gmp')) {
3227 $p = new static();
3228 $p->value = gmp_nextprime($x->value);
3229
3230 if ($p->compare($max) <= 0) {
3231 return $p;
3232 }
3233
3234 if (!$min->equals($x)) {
3235 $x = $x->subtract($one);
3236 }
3237
3238 return $x->randomPrime($min, $x);
3239 }
3240
3241 if ($x->equals($two)) {
3242 return $x;
3243 }
3244
3245 $x->_make_odd();
3246 if ($x->compare($max) > 0) {
3247 // if $x > $max then $max is even and if $min == $max then no prime number exists between the specified range
3248 if ($min->equals($max)) {
3249 return false;
3250 }
3251 $x = $min->copy();
3252 $x->_make_odd();
3253 }
3254
3255 $initial_x = $x->copy();
3256
3257 while (true) {
3258 if ($timeout !== false && time() - $start > $timeout) {
3259 return false;
3260 }
3261
3262 if ($x->isPrime()) {
3263 return $x;
3264 }
3265
3266 $x = $x->add($two);
3267
3268 if ($x->compare($max) > 0) {
3269 $x = $min->copy();
3270 if ($x->equals($two)) {
3271 return $x;
3272 }
3273 $x->_make_odd();
3274 }
3275
3276 if ($x->equals($initial_x)) {
3277 return false;
3278 }
3279 }
3280 }

References $start, $x, and phpseclib\Math\BigInteger\random().

+ Here is the call graph for this function:

◆ setPrecision()

phpseclib\Math\BigInteger::setPrecision (   $bits)

Set Precision.

Some bitwise operations give different results depending on the precision being used. Examples include left shift, not, and rotates.

Parameters
int$bits@access public

Definition at line 2755 of file BigInteger.php.

2756 {
2757 $this->precision = $bits;
2758 if (MATH_BIGINTEGER_MODE != self::MODE_BCMATH) {
2759 $this->bitmask = new static(chr((1 << ($bits & 0x7)) - 1) . str_repeat(chr(0xFF), $bits >> 3), 256);
2760 } else {
2761 $this->bitmask = new static(bcpow('2', $bits, 0));
2762 }
2763
2764 $temp = $this->_normalize($this);
2765 $this->value = $temp->value;
2766 }

References phpseclib\Math\BigInteger\_normalize().

Referenced by phpseclib\Math\BigInteger\__wakeup().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ subtract()

phpseclib\Math\BigInteger::subtract (   $y)

Subtracts two BigIntegers.

Here's an example: <?php $a = new \phpseclib\Math\BigInteger('10'); $b = new \phpseclib\Math\BigInteger('20');

$c = $a->subtract($b);

echo $c->toString(); // outputs -10 ?>

Parameters
\phpseclib\Math\BigInteger$y
Returns
\phpseclib\Math\BigInteger @access public

Definition at line 988 of file BigInteger.php.

989 {
990 switch (MATH_BIGINTEGER_MODE) {
991 case self::MODE_GMP:
992 $temp = new static();
993 $temp->value = gmp_sub($this->value, $y->value);
994
995 return $this->_normalize($temp);
997 $temp = new static();
998 $temp->value = bcsub($this->value, $y->value, 0);
999
1000 return $this->_normalize($temp);
1001 }
1002
1003 $temp = $this->_subtract($this->value, $this->is_negative, $y->value, $y->is_negative);
1004
1005 $result = new static();
1006 $result->value = $temp[self::VALUE];
1007 $result->is_negative = $temp[self::SIGN];
1008
1009 return $this->_normalize($result);
1010 }

References $result, $y, phpseclib\Math\BigInteger\_normalize(), phpseclib\Math\BigInteger\_subtract(), phpseclib\Math\BigInteger\MODE_BCMATH, phpseclib\Math\BigInteger\MODE_GMP, phpseclib\Math\BigInteger\SIGN, and phpseclib\Math\BigInteger\VALUE.

+ Here is the call graph for this function:

◆ toBits()

phpseclib\Math\BigInteger::toBits (   $twos_compliment = false)

Converts a BigInteger to a bit string (eg.

base-2).

Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're saved as two's compliment.

Here's an example: <?php $a = new \phpseclib\Math\BigInteger('65');

echo $a->toBits(); // outputs '1000001' ?>

Parameters
bool$twos_compliment
Returns
string @access public

Definition at line 642 of file BigInteger.php.

643 {
644 $hex = $this->toHex($twos_compliment);
645 $bits = '';
646 for ($i = strlen($hex) - 8, $start = strlen($hex) & 7; $i >= $start; $i-=8) {
647 $bits = str_pad(decbin(hexdec(substr($hex, $i, 8))), 32, '0', STR_PAD_LEFT) . $bits;
648 }
649 if ($start) { // hexdec('') == 0
650 $bits = str_pad(decbin(hexdec(substr($hex, 0, $start))), 8, '0', STR_PAD_LEFT) . $bits;
651 }
652 $result = $this->precision > 0 ? substr($bits, -$this->precision) : ltrim($bits, '0');
653
654 if ($twos_compliment && $this->compare(new static()) > 0 && $this->precision <= 0) {
655 return '0' . $result;
656 }
657
658 return $result;
659 }

References phpseclib\Math\BigInteger\$hex, $i, $result, $start, phpseclib\Math\BigInteger\compare(), and phpseclib\Math\BigInteger\toHex().

+ Here is the call graph for this function:

◆ toBytes()

phpseclib\Math\BigInteger::toBytes (   $twos_compliment = false)

Converts a BigInteger to a byte string (eg.

base-256).

Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're saved as two's compliment.

Here's an example: <?php $a = new \phpseclib\Math\BigInteger('65');

echo $a->toBytes(); // outputs chr(65) ?>

Parameters
bool$twos_compliment
Returns
string @access public

Definition at line 522 of file BigInteger.php.

523 {
524 if ($twos_compliment) {
525 $comparison = $this->compare(new static());
526 if ($comparison == 0) {
527 return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
528 }
529
530 $temp = $comparison < 0 ? $this->add(new static(1)) : $this->copy();
531 $bytes = $temp->toBytes();
532
533 if (empty($bytes)) { // eg. if the number we're trying to convert is -1
534 $bytes = chr(0);
535 }
536
537 if (ord($bytes[0]) & 0x80) {
538 $bytes = chr(0) . $bytes;
539 }
540
541 return $comparison < 0 ? ~$bytes : $bytes;
542 }
543
544 switch (MATH_BIGINTEGER_MODE) {
545 case self::MODE_GMP:
546 if (gmp_cmp($this->value, gmp_init(0)) == 0) {
547 return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
548 }
549
550 $temp = gmp_strval(gmp_abs($this->value), 16);
551 $temp = (strlen($temp) & 1) ? '0' . $temp : $temp;
552 $temp = pack('H*', $temp);
553
554 return $this->precision > 0 ?
555 substr(str_pad($temp, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) :
556 ltrim($temp, chr(0));
558 if ($this->value === '0') {
559 return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
560 }
561
562 $value = '';
564
565 if ($current[0] == '-') {
566 $current = substr($current, 1);
567 }
568
569 while (bccomp($current, '0', 0) > 0) {
570 $temp = bcmod($current, '16777216');
571 $value = chr($temp >> 16) . chr($temp >> 8) . chr($temp) . $value;
572 $current = bcdiv($current, '16777216', 0);
573 }
574
575 return $this->precision > 0 ?
576 substr(str_pad($value, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) :
577 ltrim($value, chr(0));
578 }
579
580 if (!count($this->value)) {
581 return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
582 }
583 $result = $this->_int2bytes($this->value[count($this->value) - 1]);
584
585 $temp = $this->copy();
586
587 for ($i = count($temp->value) - 2; $i >= 0; --$i) {
588 $temp->_base256_lshift($result, self::$base);
589 $result = $result | str_pad($temp->_int2bytes($temp->value[$i]), strlen($result), chr(0), STR_PAD_LEFT);
590 }
591
592 return $this->precision > 0 ?
593 str_pad(substr($result, -(($this->precision + 7) >> 3)), ($this->precision + 7) >> 3, chr(0), STR_PAD_LEFT) :
594 $result;
595 }

References $base, $current, $i, $result, phpseclib\Math\BigInteger\$value, phpseclib\Math\BigInteger\_int2bytes(), phpseclib\Math\BigInteger\add(), phpseclib\Math\BigInteger\compare(), phpseclib\Math\BigInteger\copy(), phpseclib\Math\BigInteger\MODE_BCMATH, and phpseclib\Math\BigInteger\MODE_GMP.

Referenced by phpseclib\Math\BigInteger\bitwise_and(), phpseclib\Math\BigInteger\bitwise_leftRotate(), phpseclib\Math\BigInteger\bitwise_not(), phpseclib\Math\BigInteger\bitwise_or(), phpseclib\Math\BigInteger\bitwise_xor(), phpseclib\Math\BigInteger\isPrime(), phpseclib\Math\BigInteger\modPow(), and phpseclib\Math\BigInteger\toHex().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ toHex()

phpseclib\Math\BigInteger::toHex (   $twos_compliment = false)

Converts a BigInteger to a hex string (eg.

base-16)).

Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're saved as two's compliment.

Here's an example: <?php $a = new \phpseclib\Math\BigInteger('65');

echo $a->toHex(); // outputs '41' ?>

Parameters
bool$twos_compliment
Returns
string @access public

Definition at line 617 of file BigInteger.php.

618 {
619 return bin2hex($this->toBytes($twos_compliment));
620 }

References phpseclib\Math\BigInteger\toBytes().

Referenced by phpseclib\Math\BigInteger\__debugInfo(), phpseclib\Math\BigInteger\__sleep(), and phpseclib\Math\BigInteger\toBits().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

◆ toString()

phpseclib\Math\BigInteger::toString ( )

Converts a BigInteger to a base-10 number.

Here's an example: <?php $a = new \phpseclib\Math\BigInteger('50');

echo $a->toString(); // outputs 50 ?>

Returns
string @access public

Definition at line 677 of file BigInteger.php.

678 {
679 switch (MATH_BIGINTEGER_MODE) {
680 case self::MODE_GMP:
681 return gmp_strval($this->value);
683 if ($this->value === '0') {
684 return '0';
685 }
686
687 return ltrim($this->value, '0');
688 }
689
690 if (!count($this->value)) {
691 return '0';
692 }
693
694 $temp = $this->copy();
695 $temp->is_negative = false;
696
697 $divisor = new static();
698 $divisor->value = array(self::$max10);
699 $result = '';
700 while (count($temp->value)) {
701 list($temp, $mod) = $temp->divide($divisor);
702 $result = str_pad(isset($mod->value[0]) ? $mod->value[0] : '', self::$max10Len, '0', STR_PAD_LEFT) . $result;
703 }
704 $result = ltrim($result, '0');
705 if (empty($result)) {
706 $result = '0';
707 }
708
709 if ($this->is_negative) {
710 $result = '-' . $result;
711 }
712
713 return $result;
714 }

References $result, phpseclib\Math\BigInteger\copy(), phpseclib\Math\BigInteger\MODE_BCMATH, and phpseclib\Math\BigInteger\MODE_GMP.

Referenced by phpseclib\Math\BigInteger\__toString().

+ Here is the call graph for this function:
+ Here is the caller graph for this function:

Field Documentation

◆ $base

phpseclib\Math\BigInteger::$base
staticprotected

#+ Static properties used by the pure-PHP implementation.

See also
__construct()

Definition at line 167 of file BigInteger.php.

Referenced by phpseclib\Math\BigInteger\__construct(), phpseclib\Math\BigInteger\_lshift(), and phpseclib\Math\BigInteger\_rshift().

◆ $baseFull

phpseclib\Math\BigInteger::$baseFull
staticprotected

◆ $bitmask

phpseclib\Math\BigInteger::$bitmask = false

Precision Bitmask.

See also
self::setPrecision() @access private

Definition at line 216 of file BigInteger.php.

Referenced by phpseclib\Math\BigInteger\_normalize(), and phpseclib\Math\BigInteger\copy().

◆ $hex

phpseclib\Math\BigInteger::$hex

◆ $is_negative

phpseclib\Math\BigInteger::$is_negative = false

◆ $max10

phpseclib\Math\BigInteger::$max10
staticprotected

$max10 in greatest $max10Len satisfying $max10 = 10**$max10Len <= 2**$base.

Definition at line 176 of file BigInteger.php.

◆ $max10Len

phpseclib\Math\BigInteger::$max10Len
staticprotected

$max10Len in greatest $max10Len satisfying $max10 = 10**$max10Len <= 2**$base.

Definition at line 182 of file BigInteger.php.

◆ $maxDigit

◆ $maxDigit2

phpseclib\Math\BigInteger::$maxDigit2
staticprotected

◆ $msb

phpseclib\Math\BigInteger::$msb
staticprotected

◆ $precision

phpseclib\Math\BigInteger::$precision = -1

Precision.

See also
self::setPrecision() @access private

Definition at line 208 of file BigInteger.php.

Referenced by phpseclib\Math\BigInteger\_normalize(), phpseclib\Math\BigInteger\bitwise_leftRotate(), and phpseclib\Math\BigInteger\copy().

◆ $value

◆ BARRETT

const phpseclib\Math\BigInteger::BARRETT = 1
See also
BigInteger::_barrett()

Definition at line 79 of file BigInteger.php.

Referenced by phpseclib\Math\BigInteger\_reduce().

◆ CLASSIC

const phpseclib\Math\BigInteger::CLASSIC = 3
See also
BigInteger::_remainder()

Definition at line 87 of file BigInteger.php.

Referenced by phpseclib\Math\BigInteger\_reduce().

◆ DATA

const phpseclib\Math\BigInteger::DATA = 1

◆ KARATSUBA_CUTOFF

const phpseclib\Math\BigInteger::KARATSUBA_CUTOFF = 25

#-

Karatsuba Cutoff

At what point do we switch between Karatsuba multiplication and schoolbook long multiplication?

@access private

Definition at line 160 of file BigInteger.php.

◆ MODE_BCMATH

◆ MODE_GMP

◆ MODE_INTERNAL

const phpseclib\Math\BigInteger::MODE_INTERNAL = 1

#-

#+ Mode constants.

@access private

See also
BigInteger::__construct() To use the pure-PHP implementation

Definition at line 138 of file BigInteger.php.

Referenced by phpseclib\Math\BigInteger\__debugInfo().

◆ MONTGOMERY

const phpseclib\Math\BigInteger::MONTGOMERY = 0

#+ Reduction constants

@access private

See also
BigInteger::_reduce()
BigInteger::_montgomery()
BigInteger::_prepMontgomery()

Definition at line 75 of file BigInteger.php.

Referenced by phpseclib\Math\BigInteger\_reduce().

◆ NONE

const phpseclib\Math\BigInteger::NONE = 4
See also
BigInteger::__clone()

Definition at line 91 of file BigInteger.php.

Referenced by phpseclib\Math\BigInteger\_reduce().

◆ POWEROF2

const phpseclib\Math\BigInteger::POWEROF2 = 2
See also
BigInteger::_mod2()

Definition at line 83 of file BigInteger.php.

Referenced by phpseclib\Math\BigInteger\_reduce().

◆ SIGN

const phpseclib\Math\BigInteger::SIGN = 1

◆ VALUE

const phpseclib\Math\BigInteger::VALUE = 0

#-

#+ Array constants

Rather than create a thousands and thousands of new BigInteger objects in repeated function calls to add() and multiply() or whatever, we'll just work directly on arrays, taking them in as parameters and returning them.

@access private $result[self::VALUE] contains the value.

Definition at line 105 of file BigInteger.php.

Referenced by phpseclib\Math\BigInteger\_barrett(), phpseclib\Math\BigInteger\_karatsuba(), phpseclib\Math\BigInteger\_karatsubaSquare(), phpseclib\Math\BigInteger\_montgomery(), phpseclib\Math\BigInteger\_montgomeryMultiply(), phpseclib\Math\BigInteger\_regularBarrett(), phpseclib\Math\BigInteger\add(), phpseclib\Math\BigInteger\multiply(), and phpseclib\Math\BigInteger\subtract().

◆ VARIABLE

const phpseclib\Math\BigInteger::VARIABLE = 0

#-

#+ @access private

See also
BigInteger::_montgomery()
BigInteger::_barrett() Cache constants

$cache[self::VARIABLE] tells us whether or not the cached data is still valid.

Definition at line 122 of file BigInteger.php.

Referenced by phpseclib\Math\BigInteger\_barrett(), phpseclib\Math\BigInteger\_montgomery(), phpseclib\Math\BigInteger\_montgomeryMultiply(), and phpseclib\Math\BigInteger\_regularBarrett().


The documentation for this class was generated from the following file: