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 ('0x32', 16); // 50 in base-16

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

Parameters

	$x	base-10 number or base-$base number if $base set.
int	$base

Returns

public

Definition at line 252 of file BigInteger.php.

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

    {
        if (!defined('MATH_BIGINTEGER_MODE')) {
            switch (true) {
                case extension_loaded('gmp'):
                    define('MATH_BIGINTEGER_MODE', self::MODE_GMP);
                    break;
                case extension_loaded('bcmath'):
                    define('MATH_BIGINTEGER_MODE', self::MODE_BCMATH);
                    break;
                default:
                    define('MATH_BIGINTEGER_MODE', self::MODE_INTERNAL);
            }
        }

        if (extension_loaded('openssl') && !defined('MATH_BIGINTEGER_OPENSSL_DISABLE') && !defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
            // some versions of XAMPP have mismatched versions of OpenSSL which causes it not to work
            ob_start();
            @phpinfo();
            $content = ob_get_contents();
            ob_end_clean();

            preg_match_all('#OpenSSL (Header|Library) Version(.*)#im', $content, $matches);

            $versions = array();
            if (!empty($matches[1])) {
                for ($i = 0; $i < count($matches[1]); $i++) {
                    $fullVersion = trim(str_replace('=>', '', strip_tags($matches[2][$i])));

                    // Remove letter part in OpenSSL version
                    if (!preg_match('/(\d+\.\d+\.\d+)/i', $fullVersion, $m)) {
                        $versions[$matches[1][$i]] = $fullVersion;
                    } else {
                        $versions[$matches[1][$i]] = $m[0];
                    }
                }
            }

            // it doesn't appear that OpenSSL versions were reported upon until PHP 5.3+
            switch (true) {
                case !isset($versions['Header']):
                case !isset($versions['Library']):
                case $versions['Header'] == $versions['Library']:
                    define('MATH_BIGINTEGER_OPENSSL_ENABLED', true);
                    break;
                default:
                    define('MATH_BIGINTEGER_OPENSSL_DISABLE', true);
            }
        }

        if (!defined('PHP_INT_SIZE')) {
            define('PHP_INT_SIZE', 4);
        }

        if (empty(self::$base) && MATH_BIGINTEGER_MODE == self::MODE_INTERNAL) {
            switch (PHP_INT_SIZE) {
                case 8: // use 64-bit integers if int size is 8 bytes
                    self::$base      = 31;
                    self::$baseFull  = 0x80000000;
                    self::$maxDigit  = 0x7FFFFFFF;
                    self::$msb       = 0x40000000;
                    self::$max10     = 1000000000;
                    self::$max10Len  = 9;
                    self::$maxDigit2 = pow(2, 62);
                    break;
                //case 4: // use 64-bit floats if int size is 4 bytes
                default:
                    self::$base      = 26;
                    self::$baseFull  = 0x4000000;
                    self::$maxDigit  = 0x3FFFFFF;
                    self::$msb       = 0x2000000;
                    self::$max10     = 10000000;
                    self::$max10Len  = 7;
                    self::$maxDigit2 = pow(2, 52); // pow() prevents truncation
            }
        }

        switch (MATH_BIGINTEGER_MODE) {
            case self::MODE_GMP:
                switch (true) {
                    case is_resource($x) && get_resource_type($x) == 'GMP integer':
                    // PHP 5.6 switched GMP from using resources to objects
                    case $x instanceof \GMP:
                        $this->value = $x;
                        return;
                }
                $this->value = gmp_init(0);
                break;
            case self::MODE_BCMATH:
                $this->value = '0';
                break;
            default:
                $this->value = array();
        }

        // '0' counts as empty() but when the base is 256 '0' is equal to ord('0') or 48
        // '0' is the only value like this per http://php.net/empty
        if (empty($x) && (abs($base) != 256 || $x !== '0')) {
            return;
        }

        switch ($base) {
            case -256:
                if (ord($x[0]) & 0x80) {
                    $x = ~$x;
                    $this->is_negative = true;
                }
            case 256:
                switch (MATH_BIGINTEGER_MODE) {
                    case self::MODE_GMP:
                        $sign = $this->is_negative ? '-' : '';
                        $this->value = gmp_init($sign . '0x' . bin2hex($x));
                        break;
                    case self::MODE_BCMATH:
                        // round $len to the nearest 4 (thanks, DavidMJ!)
                        $len = (strlen($x) + 3) & 0xFFFFFFFC;

                        $x = str_pad($x, $len, chr(0), STR_PAD_LEFT);

                        for ($i = 0; $i < $len; $i+= 4) {
                            $this->value = bcmul($this->value, '4294967296', 0); // 4294967296 == 2**32
                            $this->value = bcadd($this->value, 0x1000000 * ord($x[$i]) + ((ord($x[$i + 1]) << 16) | (ord($x[$i + 2]) << 8) | ord($x[$i + 3])), 0);
                        }

                        if ($this->is_negative) {
                            $this->value = '-' . $this->value;
                        }

                        break;
                    // converts a base-2**8 (big endian / msb) number to base-2**26 (little endian / lsb)
                    default:
                        while (strlen($x)) {
                            $this->value[] = $this->_bytes2int($this->_base256_rshift($x, self::$base));
                        }
                }

                if ($this->is_negative) {
                    if (MATH_BIGINTEGER_MODE != self::MODE_INTERNAL) {
                        $this->is_negative = false;
                    }
                    $temp = $this->add(new static('-1'));
                    $this->value = $temp->value;
                }
                break;
            case 16:
            case -16:
                if ($base > 0 && $x[0] == '-') {
                    $this->is_negative = true;
                    $x = substr($x, 1);
                }

                $x = preg_replace('#^(?:0x)?([A-Fa-f0-9]*).*#', '$1', $x);

                $is_negative = false;
                if ($base < 0 && hexdec($x[0]) >= 8) {
                    $this->is_negative = $is_negative = true;
                    $x = bin2hex(~pack('H*', $x));
                }

                switch (MATH_BIGINTEGER_MODE) {
                    case self::MODE_GMP:
                        $temp = $this->is_negative ? '-0x' . $x : '0x' . $x;
                        $this->value = gmp_init($temp);
                        $this->is_negative = false;
                        break;
                    case self::MODE_BCMATH:
                        $x = (strlen($x) & 1) ? '0' . $x : $x;
                        $temp = new static(pack('H*', $x), 256);
                        $this->value = $this->is_negative ? '-' . $temp->value : $temp->value;
                        $this->is_negative = false;
                        break;
                    default:
                        $x = (strlen($x) & 1) ? '0' . $x : $x;
                        $temp = new static(pack('H*', $x), 256);
                        $this->value = $temp->value;
                }

                if ($is_negative) {
                    $temp = $this->add(new static('-1'));
                    $this->value = $temp->value;
                }
                break;
            case 10:
            case -10:
                // (?<!^)(?:-).*: find any -'s that aren't at the beginning and then any characters that follow that
                // (?<=^|-)0*: find any 0's that are preceded by the start of the string or by a - (ie. octals)
                // [^-0-9].*: find any non-numeric characters and then any characters that follow that
                $x = preg_replace('#(?<!^)(?:-).*|(?<=^|-)0*|[^-0-9].*#', '', $x);

                switch (MATH_BIGINTEGER_MODE) {
                    case self::MODE_GMP:
                        $this->value = gmp_init($x);
                        break;
                    case self::MODE_BCMATH:
                        // explicitly casting $x to a string is necessary, here, since doing $x[0] on -1 yields different
                        // results then doing it on '-1' does (modInverse does $x[0])
                        $this->value = $x === '-' ? '0' : (string) $x;
                        break;
                    default:
                        $temp = new static();

                        $multiplier = new static();
                        $multiplier->value = array(self::$max10);

                        if ($x[0] == '-') {
                            $this->is_negative = true;
                            $x = substr($x, 1);
                        }

                        $x = str_pad($x, strlen($x) + ((self::$max10Len - 1) * strlen($x)) % self::$max10Len, 0, STR_PAD_LEFT);
                        while (strlen($x)) {
                            $temp = $temp->multiply($multiplier);
                            $temp = $temp->add(new static($this->_int2bytes(substr($x, 0, self::$max10Len)), 256));
                            $x = substr($x, self::$max10Len);
                        }

                        $this->value = $temp->value;
                }
                break;
            case 2: // base-2 support originally implemented by Lluis Pamies - thanks!
            case -2:
                if ($base > 0 && $x[0] == '-') {
                    $this->is_negative = true;
                    $x = substr($x, 1);
                }

                $x = preg_replace('#^([01]*).*#', '$1', $x);
                $x = str_pad($x, strlen($x) + (3 * strlen($x)) % 4, 0, STR_PAD_LEFT);

                $str = '0x';
                while (strlen($x)) {
                    $part = substr($x, 0, 4);
                    $str.= dechex(bindec($part));
                    $x = substr($x, 4);
                }

                if ($this->is_negative) {
                    $str = '-' . $str;
                }

                $temp = new static($str, 8 * $base); // ie. either -16 or +16
                $this->value = $temp->value;
                $this->is_negative = $temp->is_negative;

                break;
            default:
                // base not supported, so we'll let $this == 0
        }
    }

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.

public

See also

self::copy()

Returns

Definition at line 764 of file BigInteger.php.

References phpseclib\Math\BigInteger\copy().

    {
        return $this->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

public

Definition at line 813 of file BigInteger.php.

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

    {
        $opts = array();
        switch (MATH_BIGINTEGER_MODE) {
            case self::MODE_GMP:
                $engine = 'gmp';
                break;
            case self::MODE_BCMATH:
                $engine = 'bcmath';
                break;
            case self::MODE_INTERNAL:
                $engine = 'internal';
                $opts[] = PHP_INT_SIZE == 8 ? '64-bit' : '32-bit';
        }
        if (MATH_BIGINTEGER_MODE != self::MODE_GMP && defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
            $opts[] = 'OpenSSL';
        }
        if (!empty($opts)) {
            $engine.= ' (' . implode($opts, ', ') . ')';
        }
        return array(
            'value' => '0x' . $this->toHex(true),
            'engine' => $engine
        );
    }

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() User interface

Definition at line 777 of file BigInteger.php.

References phpseclib\Math\BigInteger\toHex().

    {
        $this->hex = $this->toHex(true);
        $vars = array('hex');
        if ($this->precision > 0) {
            $vars[] = 'precision';
        }
        return $vars;
    }

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().

public

Definition at line 747 of file BigInteger.php.

References phpseclib\Math\BigInteger\toString().

    {
        return $this->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() User interface

Definition at line 795 of file BigInteger.php.

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

    {
        $temp = new static($this->hex, -16);
        $this->value = $temp->value;
        $this->is_negative = $temp->is_negative;
        if ($this->precision > 0) {
            // recalculate $this->bitmask
            $this->setPrecision($this->precision);
        }
    }

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 private

Definition at line 893 of file BigInteger.php.

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

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().

    {
        $x_size = count($x_value);
        $y_size = count($y_value);

        if ($x_size == 0) {
            return array(
                self::VALUE => $y_value,
                self::SIGN => $y_negative
            );
        } elseif ($y_size == 0) {
            return array(
                self::VALUE => $x_value,
                self::SIGN => $x_negative
            );
        }

        // subtract, if appropriate
        if ($x_negative != $y_negative) {
            if ($x_value == $y_value) {
                return array(
                    self::VALUE => array(),
                    self::SIGN => false
                );
            }

            $temp = $this->_subtract($x_value, false, $y_value, false);
            $temp[self::SIGN] = $this->_compare($x_value, false, $y_value, false) > 0 ?
                                          $x_negative : $y_negative;

            return $temp;
        }

        if ($x_size < $y_size) {
            $size = $x_size;
            $value = $y_value;
        } else {
            $size = $y_size;
            $value = $x_value;
        }

        $value[count($value)] = 0; // just in case the carry adds an extra digit

        $carry = 0;
        for ($i = 0, $j = 1; $j < $size; $i+=2, $j+=2) {
            $sum = $x_value[$j] * self::$baseFull + $x_value[$i] + $y_value[$j] * self::$baseFull + $y_value[$i] + $carry;
            $carry = $sum >= self::$maxDigit2; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1
            $sum = $carry ? $sum - self::$maxDigit2 : $sum;

            $temp = self::$base === 26 ? intval($sum / 0x4000000) : ($sum >> 31);

            $value[$i] = (int) ($sum - self::$baseFull * $temp); // eg. a faster alternative to fmod($sum, 0x4000000)
            $value[$j] = $temp;
        }

        if ($j == $size) { // ie. if $y_size is odd
            $sum = $x_value[$i] + $y_value[$i] + $carry;
            $carry = $sum >= self::$baseFull;
            $value[$i] = $carry ? $sum - self::$baseFull : $sum;
            ++$i; // ie. let $i = $j since we've just done $value[$i]
        }

        if ($carry) {
            for (; $value[$i] == self::$maxDigit; ++$i) {
                $value[$i] = 0;
            }
            ++$value[$i];
        }

        return array(
            self::VALUE => $this->_trim($value),
            self::SIGN => $x_negative
        );
    }

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

$input	Array
$multiplier	mixed

Returns

array private

Definition at line 3609 of file BigInteger.php.

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().

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

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() private

Parameters

array	$n
array	$m

Returns

array

Definition at line 2013 of file BigInteger.php.

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(), and phpseclib\Math\BigInteger\_trim().

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

    {
        static $cache = array(
            self::VARIABLE => array(),
            self::DATA => array()
        );

        $m_length = count($m);

        // if ($this->_compare($n, $this->_square($m)) >= 0) {
        if (count($n) > 2 * $m_length) {
            $lhs = new static();
            $rhs = new static();
            $lhs->value = $n;
            $rhs->value = $m;
            list(, $temp) = $lhs->divide($rhs);
            return $temp->value;
        }

        // if (m.length >> 1) + 2 <= m.length then m is too small and n can't be reduced
        if ($m_length < 5) {
            return $this->_regularBarrett($n, $m);
        }

        // n = 2 * m.length

        if (($key = array_search($m, $cache[self::VARIABLE])) === false) {
            $key = count($cache[self::VARIABLE]);
            $cache[self::VARIABLE][] = $m;

            $lhs = new static();
            $lhs_value = &$lhs->value;
            $lhs_value = $this->_array_repeat(0, $m_length + ($m_length >> 1));
            $lhs_value[] = 1;
            $rhs = new static();
            $rhs->value = $m;

            list($u, $m1) = $lhs->divide($rhs);
            $u = $u->value;
            $m1 = $m1->value;

            $cache[self::DATA][] = array(
                'u' => $u, // m.length >> 1 (technically (m.length >> 1) + 1)
                'm1'=> $m1 // m.length
            );
        } else {
            extract($cache[self::DATA][$key]);
        }

        $cutoff = $m_length + ($m_length >> 1);
        $lsd = array_slice($n, 0, $cutoff); // m.length + (m.length >> 1)
        $msd = array_slice($n, $cutoff);    // m.length >> 1
        $lsd = $this->_trim($lsd);
        $temp = $this->_multiply($msd, false, $m1, false);
        $n = $this->_add($lsd, false, $temp[self::VALUE], false); // m.length + (m.length >> 1) + 1

        if ($m_length & 1) {
            return $this->_regularBarrett($n[self::VALUE], $m);
        }

        // (m.length + (m.length >> 1) + 1) - (m.length - 1) == (m.length >> 1) + 2
        $temp = array_slice($n[self::VALUE], $m_length - 1);
        // if even: ((m.length >> 1) + 2) + (m.length >> 1) == m.length + 2
        // if odd:  ((m.length >> 1) + 2) + (m.length >> 1) == (m.length - 1) + 2 == m.length + 1
        $temp = $this->_multiply($temp, false, $u, false);
        // if even: (m.length + 2) - ((m.length >> 1) + 1) = m.length - (m.length >> 1) + 1
        // if odd:  (m.length + 1) - ((m.length >> 1) + 1) = m.length - (m.length >> 1)
        $temp = array_slice($temp[self::VALUE], ($m_length >> 1) + 1);
        // if even: (m.length - (m.length >> 1) + 1) + m.length = 2 * m.length - (m.length >> 1) + 1
        // if odd:  (m.length - (m.length >> 1)) + m.length     = 2 * m.length - (m.length >> 1)
        $temp = $this->_multiply($temp, false, $m, false);

        // at this point, if m had an odd number of digits, we'd be subtracting a 2 * m.length - (m.length >> 1) digit
        // number from a m.length + (m.length >> 1) + 1 digit number.  ie. there'd be an extra digit and the while loop
        // following this comment would loop a lot (hence our calling _regularBarrett() in that situation).

        $result = $this->_subtract($n[self::VALUE], false, $temp[self::VALUE], false);

        while ($this->_compare($result[self::VALUE], $result[self::SIGN], $m, false) >= 0) {
            $result = $this->_subtract($result[self::VALUE], $result[self::SIGN], $m, false);
        }

        return $result[self::VALUE];
    }

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

$x	String
$shift	Integer

Returns

string private

Definition at line 3624 of file BigInteger.php.

References $i, and $x.

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

    {
        if ($shift == 0) {
            return;
        }

        $num_bytes = $shift >> 3; // eg. floor($shift/8)
        $shift &= 7; // eg. $shift % 8

        $carry = 0;
        for ($i = strlen($x) - 1; $i >= 0; --$i) {
            $temp = ord($x[$i]) << $shift | $carry;
            $x[$i] = chr($temp);
            $carry = $temp >> 8;
        }
        $carry = ($carry != 0) ? chr($carry) : '';
        $x = $carry . $x . str_repeat(chr(0), $num_bytes);
    }

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

$x	String
$shift	Integer

Returns

string private

Definition at line 3653 of file BigInteger.php.

References $i, $start, and $x.

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

    {
        if ($shift == 0) {
            $x = ltrim($x, chr(0));
            return '';
        }

        $num_bytes = $shift >> 3; // eg. floor($shift/8)
        $shift &= 7; // eg. $shift % 8

        $remainder = '';
        if ($num_bytes) {
            $start = $num_bytes > strlen($x) ? -strlen($x) : -$num_bytes;
            $remainder = substr($x, $start);
            $x = substr($x, 0, -$num_bytes);
        }

        $carry = 0;
        $carry_shift = 8 - $shift;
        for ($i = 0; $i < strlen($x); ++$i) {
            $temp = (ord($x[$i]) >> $shift) | $carry;
            $carry = (ord($x[$i]) << $carry_shift) & 0xFF;
            $x[$i] = chr($temp);
        }
        $x = ltrim($x, chr(0));

        $remainder = chr($carry >> $carry_shift) . $remainder;

        return ltrim($remainder, chr(0));
    }

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 private

Definition at line 1312 of file BigInteger.php.

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

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

    {
        if (empty($value)) {
            return array();
        }
        $square_value = $this->_array_repeat(0, 2 * count($value));

        for ($i = 0, $max_index = count($value) - 1; $i <= $max_index; ++$i) {
            $i2 = $i << 1;

            $temp = $square_value[$i2] + $value[$i] * $value[$i];
            $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
            $square_value[$i2] = (int) ($temp - self::$baseFull * $carry);

            // note how we start from $i+1 instead of 0 as we do in multiplication.
            for ($j = $i + 1, $k = $i2 + 1; $j <= $max_index; ++$j, ++$k) {
                $temp = $square_value[$k] + 2 * $value[$j] * $value[$i] + $carry;
                $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
                $square_value[$k] = (int) ($temp - self::$baseFull * $carry);
            }

            // the following line can yield values larger 2**15.  at this point, PHP should switch
            // over to floats.
            $square_value[$i + $max_index + 1] = $carry;
        }

        return $square_value;
    }

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 private

Definition at line 3706 of file BigInteger.php.

References $x.

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

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

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() private

Definition at line 2701 of file BigInteger.php.

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().

    {
        if ($x_negative != $y_negative) {
            return (!$x_negative && $y_negative) ? 1 : -1;
        }

        $result = $x_negative ? -1 : 1;

        if (count($x_value) != count($y_value)) {
            return (count($x_value) > count($y_value)) ? $result : -$result;
        }
        $size = max(count($x_value), count($y_value));

        $x_value = array_pad($x_value, $size, 0);
        $y_value = array_pad($y_value, $size, 0);

        for ($i = count($x_value) - 1; $i >= 0; --$i) {
            if ($x_value[$i] != $y_value[$i]) {
                return ($x_value[$i] > $y_value[$i]) ? $result : -$result;
            }
        }

        return 0;
    }

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 private

Definition at line 1587 of file BigInteger.php.

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

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

    {
        $carry = 0;
        $result = array();

        for ($i = count($dividend) - 1; $i >= 0; --$i) {
            $temp = self::$baseFull * $carry + $dividend[$i];
            $result[$i] = $this->_safe_divide($temp, $divisor);
            $carry = (int) ($temp - $divisor * $result[$i]);
        }

        return array($result, $carry);
    }

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() private

Parameters

int

$length

Returns

string

Definition at line 3722 of file BigInteger.php.

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

    {
        if ($length <= 0x7F) {
            return chr($length);
        }

        $temp = ltrim(pack('N', $length), chr(0));
        return pack('Ca*', 0x80 | strlen($temp), $temp);
    }

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 private

Definition at line 3694 of file BigInteger.php.

References $x.

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

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

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 private

Definition at line 1256 of file BigInteger.php.

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

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

    {
        $m = min(count($x_value) >> 1, count($y_value) >> 1);

        if ($m < self::KARATSUBA_CUTOFF) {
            return $this->_regularMultiply($x_value, $y_value);
        }

        $x1 = array_slice($x_value, $m);
        $x0 = array_slice($x_value, 0, $m);
        $y1 = array_slice($y_value, $m);
        $y0 = array_slice($y_value, 0, $m);

        $z2 = $this->_karatsuba($x1, $y1);
        $z0 = $this->_karatsuba($x0, $y0);

        $z1 = $this->_add($x1, false, $x0, false);
        $temp = $this->_add($y1, false, $y0, false);
        $z1 = $this->_karatsuba($z1[self::VALUE], $temp[self::VALUE]);
        $temp = $this->_add($z2, false, $z0, false);
        $z1 = $this->_subtract($z1, false, $temp[self::VALUE], false);

        $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2);
        $z1[self::VALUE] = array_merge(array_fill(0, $m, 0), $z1[self::VALUE]);

        $xy = $this->_add($z2, false, $z1[self::VALUE], $z1[self::SIGN]);
        $xy = $this->_add($xy[self::VALUE], $xy[self::SIGN], $z0, false);

        return $xy[self::VALUE];
    }

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 private

Definition at line 1351 of file BigInteger.php.

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

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

    {
        $m = count($value) >> 1;

        if ($m < self::KARATSUBA_CUTOFF) {
            return $this->_baseSquare($value);
        }

        $x1 = array_slice($value, $m);
        $x0 = array_slice($value, 0, $m);

        $z2 = $this->_karatsubaSquare($x1);
        $z0 = $this->_karatsubaSquare($x0);

        $z1 = $this->_add($x1, false, $x0, false);
        $z1 = $this->_karatsubaSquare($z1[self::VALUE]);
        $temp = $this->_add($z2, false, $z0, false);
        $z1 = $this->_subtract($z1, false, $temp[self::VALUE], false);

        $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2);
        $z1[self::VALUE] = array_merge(array_fill(0, $m, 0), $z1[self::VALUE]);

        $xx = $this->_add($z2, false, $z1[self::VALUE], $z1[self::SIGN]);
        $xx = $this->_add($xx[self::VALUE], $xx[self::SIGN], $z0, false);

        return $xx[self::VALUE];
    }

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

private

Definition at line 3469 of file BigInteger.php.

References $base, and $i.

    {
        if ($shift == 0) {
            return;
        }

        $num_digits = (int) ($shift / self::$base);
        $shift %= self::$base;
        $shift = 1 << $shift;

        $carry = 0;

        for ($i = 0; $i < count($this->value); ++$i) {
            $temp = $this->value[$i] * $shift + $carry;
            $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
            $this->value[$i] = (int) ($temp - $carry * self::$baseFull);
        }

        if ($carry) {
            $this->value[count($this->value)] = $carry;
        }

        while ($num_digits--) {
            array_unshift($this->value, 0);
        }
    }

_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() private

Definition at line 3290 of file BigInteger.php.

    {
        switch (MATH_BIGINTEGER_MODE) {
            case self::MODE_GMP:
                gmp_setbit($this->value, 0);
                break;
            case self::MODE_BCMATH:
                if ($this->value[strlen($this->value) - 1] % 2 == 0) {
                    $this->value = bcadd($this->value, '1');
                }
                break;
            default:
                $this->value[0] |= 1;
        }
    }

_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() private

Parameters

Definition at line 1982 of file BigInteger.php.

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

    {
        $temp = new static();
        $temp->value = array(1);
        return $this->bitwise_and($n->subtract($temp));
    }

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() private

Parameters

array

$x

Returns

int

Definition at line 2399 of file BigInteger.php.

References $result, and $x.

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

    {
        $x = -$x[0];
        $result = $x & 0x3; // x**-1 mod 2**2
        $result = ($result * (2 - $x * $result)) & 0xF; // x**-1 mod 2**4
        $result = ($result * (2 - ($x & 0xFF) * $result))  & 0xFF; // x**-1 mod 2**8
        $result = ($result * ((2 - ($x & 0xFFFF) * $result) & 0xFFFF)) & 0xFFFF; // x**-1 mod 2**16
        $result = fmod($result * (2 - fmod($x * $result, self::$baseFull)), self::$baseFull); // x**-1 mod 2**26
        return $result & self::$maxDigit;
    }

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() private

Parameters

array	$x
array	$n

Returns

array

Definition at line 2263 of file BigInteger.php.

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(), and phpseclib\Math\BigInteger\_subtract().

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

    {
        static $cache = array(
            self::VARIABLE => array(),
            self::DATA => array()
        );

        if (($key = array_search($n, $cache[self::VARIABLE])) === false) {
            $key = count($cache[self::VARIABLE]);
            $cache[self::VARIABLE][] = $x;
            $cache[self::DATA][] = $this->_modInverse67108864($n);
        }

        $k = count($n);

        $result = array(self::VALUE => $x);

        for ($i = 0; $i < $k; ++$i) {
            $temp = $result[self::VALUE][$i] * $cache[self::DATA][$key];
            $temp = $temp - self::$baseFull * (self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31));
            $temp = $this->_regularMultiply(array($temp), $n);
            $temp = array_merge($this->_array_repeat(0, $i), $temp);
            $result = $this->_add($result[self::VALUE], false, $temp, false);
        }

        $result[self::VALUE] = array_slice($result[self::VALUE], $k);

        if ($this->_compare($result, false, $n, false) >= 0) {
            $result = $this->_subtract($result[self::VALUE], false, $n, false);
        }

        return $result[self::VALUE];
    }

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() private

Parameters

array	$x
array	$y
array	$m

Returns

array

Definition at line 2311 of file BigInteger.php.

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(), and phpseclib\Math\BigInteger\_subtract().

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

    {
        $temp = $this->_multiply($x, false, $y, false);
        return $this->_montgomery($temp[self::VALUE], $m);

        // the following code, although not callable, can be run independently of the above code
        // although the above code performed better in my benchmarks the following could might
        // perform better under different circumstances. in lieu of deleting it it's just been
        // made uncallable

        static $cache = array(
            self::VARIABLE => array(),
            self::DATA => array()
        );

        if (($key = array_search($m, $cache[self::VARIABLE])) === false) {
            $key = count($cache[self::VARIABLE]);
            $cache[self::VARIABLE][] = $m;
            $cache[self::DATA][] = $this->_modInverse67108864($m);
        }

        $n = max(count($x), count($y), count($m));
        $x = array_pad($x, $n, 0);
        $y = array_pad($y, $n, 0);
        $m = array_pad($m, $n, 0);
        $a = array(self::VALUE => $this->_array_repeat(0, $n + 1));
        for ($i = 0; $i < $n; ++$i) {
            $temp = $a[self::VALUE][0] + $x[$i] * $y[0];
            $temp = $temp - self::$baseFull * (self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31));
            $temp = $temp * $cache[self::DATA][$key];
            $temp = $temp - self::$baseFull * (self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31));
            $temp = $this->_add($this->_regularMultiply(array($x[$i]), $y), false, $this->_regularMultiply(array($temp), $m), false);
            $a = $this->_add($a[self::VALUE], false, $temp[self::VALUE], false);
            $a[self::VALUE] = array_slice($a[self::VALUE], 1);
        }
        if ($this->_compare($a[self::VALUE], false, $m, false) >= 0) {
            $a = $this->_subtract($a[self::VALUE], false, $m, false);
        }
        return $a[self::VALUE];
    }

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 private

Definition at line 1155 of file BigInteger.php.

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().

    {
        //if ( $x_value == $y_value ) {
        //    return array(
        //        self::VALUE => $this->_square($x_value),
        //        self::SIGN => $x_sign != $y_value
        //    );
        //}

        $x_length = count($x_value);
        $y_length = count($y_value);

        if (!$x_length || !$y_length) { // a 0 is being multiplied
            return array(
                self::VALUE => array(),
                self::SIGN => false
            );
        }

        return array(
            self::VALUE => min($x_length, $y_length) < 2 * self::KARATSUBA_CUTOFF ?
                $this->_trim($this->_regularMultiply($x_value, $y_value)) :
                $this->_trim($this->_karatsuba($x_value, $y_value)),
            self::SIGN => $x_negative != $y_negative
        );
    }

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 private

Definition at line 2184 of file BigInteger.php.

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

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

    {
        $x_length = count($x_value);
        $y_length = count($y_value);

        if (!$x_length || !$y_length) { // a 0 is being multiplied
            return array(
                self::VALUE => array(),
                self::SIGN => false
            );
        }

        if ($x_length < $y_length) {
            $temp = $x_value;
            $x_value = $y_value;
            $y_value = $temp;

            $x_length = count($x_value);
            $y_length = count($y_value);
        }

        $product_value = $this->_array_repeat(0, $x_length + $y_length);

        // the following for loop could be removed if the for loop following it
        // (the one with nested for loops) initially set $i to 0, but
        // doing so would also make the result in one set of unnecessary adds,
        // since on the outermost loops first pass, $product->value[$k] is going
        // to always be 0

        $carry = 0;

        for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0, $k = $i
            $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0
            $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
            $product_value[$j] = (int) ($temp - self::$baseFull * $carry);
        }

        if ($j < $stop) {
            $product_value[$j] = $carry;
        }

        // the above for loop is what the previous comment was talking about.  the
        // following for loop is the "one with nested for loops"

        for ($i = 1; $i < $y_length; ++$i) {
            $carry = 0;

            for ($j = 0, $k = $i; $j < $x_length && $k < $stop; ++$j, ++$k) {
                $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry;
                $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
                $product_value[$k] = (int) ($temp - self::$baseFull * $carry);
            }

            if ($k < $stop) {
                $product_value[$k] = $carry;
            }
        }

        return array(
            self::VALUE => $this->_trim($product_value),
            self::SIGN => $x_negative != $y_negative
        );
    }

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() private

Parameters

array	$x
array	$y
array	$n
int	$mode

Returns

array

Definition at line 1944 of file BigInteger.php.

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

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

    {
        if ($mode == self::MONTGOMERY) {
            return $this->_montgomeryMultiply($x, $y, $n);
        }
        $temp = $this->_multiply($x, false, $y, false);
        return $this->_reduce($temp[self::VALUE], $n, $mode);
    }

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

Definition at line 3540 of file BigInteger.php.

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

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().

    {
        $result->precision = $this->precision;
        $result->bitmask = $this->bitmask;

        switch (MATH_BIGINTEGER_MODE) {
            case self::MODE_GMP:
                if ($this->bitmask !== false) {
                    $result->value = gmp_and($result->value, $result->bitmask->value);
                }

                return $result;
            case self::MODE_BCMATH:
                if (!empty($result->bitmask->value)) {
                    $result->value = bcmod($result->value, $result->bitmask->value);
                }

                return $result;
        }

        $value = &$result->value;

        if (!count($value)) {
            return $result;
        }

        $value = $this->_trim($value);

        if (!empty($result->bitmask->value)) {
            $length = min(count($value), count($this->bitmask->value));
            $value = array_slice($value, 0, $length);

            for ($i = 0; $i < $length; ++$i) {
                $value[$i] = $value[$i] & $this->bitmask->value[$i];
            }
        }

        return $result;
    }

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() private

Parameters

array	$x
array	$n
int	$mode

Returns

array

Definition at line 1925 of file BigInteger.php.

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

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

    {
        if ($mode == self::MONTGOMERY) {
            return $this->_prepMontgomery($x, $n);
        }
        return $this->_reduce($x, $n, $mode);
    }

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() private

Parameters

array	$x
array	$n

Returns

array

Definition at line 2362 of file BigInteger.php.

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

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

    {
        $lhs = new static();
        $lhs->value = array_merge($this->_array_repeat(0, count($n)), $x);
        $rhs = new static();
        $rhs->value = $n;

        list(, $temp) = $lhs->divide($rhs);
        return $temp->value;
    }

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 if it's loaded and mt_rand if it's not.

Parameters

int

$length

Returns

private

Definition at line 3072 of file BigInteger.php.

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

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

    {
        if (class_exists('\phpseclib\Crypt\Random')) {
            $random = Random::string($size);
        } else {
            $random = '';

            if ($size & 1) {
                $random.= chr(mt_rand(0, 255));
            }

            $blocks = $size >> 1;
            for ($i = 0; $i < $blocks; ++$i) {
                // mt_rand(-2147483648, 0x7FFFFFFF) always produces -2147483648 on some systems
                $random.= pack('n', mt_rand(0, 0xFFFF));
            }
        }

        return new static($random, 256);
    }

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() private

Parameters

array	$x
array	$n
int	$mode

Returns

array

Definition at line 1888 of file BigInteger.php.

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

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

    {
        switch ($mode) {
            case self::MONTGOMERY:
                return $this->_montgomery($x, $n);
            case self::BARRETT:
                return $this->_barrett($x, $n);
            case self::POWEROF2:
                $lhs = new static();
                $lhs->value = $x;
                $rhs = new static();
                $rhs->value = $n;
                return $x->_mod2($n);
            case self::CLASSIC:
                $lhs = new static();
                $lhs->value = $x;
                $rhs = new static();
                $rhs->value = $n;
                list(, $temp) = $lhs->divide($rhs);
                return $temp->value;
            case self::NONE:
                return $x;
            default:
                // an invalid $mode was provided
        }
    }

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() private

Parameters

array	$x
array	$n

Returns

array

Definition at line 2110 of file BigInteger.php.

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(), and phpseclib\Math\BigInteger\_subtract().

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

    {
        static $cache = array(
            self::VARIABLE => array(),
            self::DATA => array()
        );

        $n_length = count($n);

        if (count($x) > 2 * $n_length) {
            $lhs = new static();
            $rhs = new static();
            $lhs->value = $x;
            $rhs->value = $n;
            list(, $temp) = $lhs->divide($rhs);
            return $temp->value;
        }

        if (($key = array_search($n, $cache[self::VARIABLE])) === false) {
            $key = count($cache[self::VARIABLE]);
            $cache[self::VARIABLE][] = $n;
            $lhs = new static();
            $lhs_value = &$lhs->value;
            $lhs_value = $this->_array_repeat(0, 2 * $n_length);
            $lhs_value[] = 1;
            $rhs = new static();
            $rhs->value = $n;
            list($temp, ) = $lhs->divide($rhs); // m.length
            $cache[self::DATA][] = $temp->value;
        }

        // 2 * m.length - (m.length - 1) = m.length + 1
        $temp = array_slice($x, $n_length - 1);
        // (m.length + 1) + m.length = 2 * m.length + 1
        $temp = $this->_multiply($temp, false, $cache[self::DATA][$key], false);
        // (2 * m.length + 1) - (m.length - 1) = m.length + 2
        $temp = array_slice($temp[self::VALUE], $n_length + 1);

        // m.length + 1
        $result = array_slice($x, 0, $n_length + 1);
        // m.length + 1
        $temp = $this->_multiplyLower($temp, false, $n, false, $n_length + 1);
        // $temp == array_slice($temp->_multiply($temp, false, $n, false)->value, 0, $n_length + 1)

        if ($this->_compare($result, false, $temp[self::VALUE], $temp[self::SIGN]) < 0) {
            $corrector_value = $this->_array_repeat(0, $n_length + 1);
            $corrector_value[count($corrector_value)] = 1;
            $result = $this->_add($result, false, $corrector_value, false);
            $result = $result[self::VALUE];
        }

        // at this point, we're subtracting a number with m.length + 1 digits from another number with m.length + 1 digits
        $result = $this->_subtract($result, false, $temp[self::VALUE], $temp[self::SIGN]);
        while ($this->_compare($result[self::VALUE], $result[self::SIGN], $n, false) > 0) {
            $result = $this->_subtract($result[self::VALUE], $result[self::SIGN], $n, false);
        }

        return $result[self::VALUE];
    }

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 private

Definition at line 1192 of file BigInteger.php.

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().

    {
        $x_length = count($x_value);
        $y_length = count($y_value);

        if (!$x_length || !$y_length) { // a 0 is being multiplied
            return array();
        }

        if ($x_length < $y_length) {
            $temp = $x_value;
            $x_value = $y_value;
            $y_value = $temp;

            $x_length = count($x_value);
            $y_length = count($y_value);
        }

        $product_value = $this->_array_repeat(0, $x_length + $y_length);

        // the following for loop could be removed if the for loop following it
        // (the one with nested for loops) initially set $i to 0, but
        // doing so would also make the result in one set of unnecessary adds,
        // since on the outermost loops first pass, $product->value[$k] is going
        // to always be 0

        $carry = 0;

        for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0
            $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0
            $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
            $product_value[$j] = (int) ($temp - self::$baseFull * $carry);
        }

        $product_value[$j] = $carry;

        // the above for loop is what the previous comment was talking about.  the
        // following for loop is the "one with nested for loops"
        for ($i = 1; $i < $y_length; ++$i) {
            $carry = 0;

            for ($j = 0, $k = $i; $j < $x_length; ++$j, ++$k) {
                $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry;
                $carry = self::$base === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
                $product_value[$k] = (int) ($temp - self::$baseFull * $carry);
            }

            $product_value[$k] = $carry;
        }

        return $product_value;
    }

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

private

Definition at line 3504 of file BigInteger.php.

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

    {
        if ($shift == 0) {
            return;
        }

        $num_digits = (int) ($shift / self::$base);
        $shift %= self::$base;
        $carry_shift = self::$base - $shift;
        $carry_mask = (1 << $shift) - 1;

        if ($num_digits) {
            $this->value = array_slice($this->value, $num_digits);
        }

        $carry = 0;

        for ($i = count($this->value) - 1; $i >= 0; --$i) {
            $temp = $this->value[$i] >> $shift | $carry;
            $carry = ($this->value[$i] & $carry_mask) << $carry_shift;
            $this->value[$i] = $temp;
        }

        $this->value = $this->_trim($this->value);
    }

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.

private

Parameters

int	$x
int	$y

Returns

int

Definition at line 3745 of file BigInteger.php.

References $base, $x, and $y.

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

    {
        if (self::$base === 26) {
            return (int) ($x / $y);
        }

        // self::$base === 31
        return ($x - ($x % $y)) / $y;
    }

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

private

Definition at line 1811 of file BigInteger.php.

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().

    {
        static $window_ranges = array(7, 25, 81, 241, 673, 1793); // from BigInteger.java's oddModPow function
        //static $window_ranges = array(0, 7, 36, 140, 450, 1303, 3529); // from MPM 7.3.1

        $e_value = $e->value;
        $e_length = count($e_value) - 1;
        $e_bits = decbin($e_value[$e_length]);
        for ($i = $e_length - 1; $i >= 0; --$i) {
            $e_bits.= str_pad(decbin($e_value[$i]), self::$base, '0', STR_PAD_LEFT);
        }

        $e_length = strlen($e_bits);

        // calculate the appropriate window size.
        // $window_size == 3 if $window_ranges is between 25 and 81, for example.
        for ($i = 0, $window_size = 1; $e_length > $window_ranges[$i] && $i < count($window_ranges); ++$window_size, ++$i) {
        }

        $n_value = $n->value;

        // precompute $this^0 through $this^$window_size
        $powers = array();
        $powers[1] = $this->_prepareReduce($this->value, $n_value, $mode);
        $powers[2] = $this->_squareReduce($powers[1], $n_value, $mode);

        // we do every other number since substr($e_bits, $i, $j+1) (see below) is supposed to end
        // in a 1.  ie. it's supposed to be odd.
        $temp = 1 << ($window_size - 1);
        for ($i = 1; $i < $temp; ++$i) {
            $i2 = $i << 1;
            $powers[$i2 + 1] = $this->_multiplyReduce($powers[$i2 - 1], $powers[2], $n_value, $mode);
        }

        $result = array(1);
        $result = $this->_prepareReduce($result, $n_value, $mode);

        for ($i = 0; $i < $e_length;) {
            if (!$e_bits[$i]) {
                $result = $this->_squareReduce($result, $n_value, $mode);
                ++$i;
            } else {
                for ($j = $window_size - 1; $j > 0; --$j) {
                    if (!empty($e_bits[$i + $j])) {
                        break;
                    }
                }

                // eg. the length of substr($e_bits, $i, $j + 1)
                for ($k = 0; $k <= $j; ++$k) {
                    $result = $this->_squareReduce($result, $n_value, $mode);
                }

                $result = $this->_multiplyReduce($result, $powers[bindec(substr($e_bits, $i, $j + 1))], $n_value, $mode);

                $i += $j + 1;
            }
        }

        $temp = new static();
        $temp->value = $this->_reduce($result, $n_value, $mode);

        return $temp;
    }

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 private

Definition at line 1294 of file BigInteger.php.

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().

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

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() private

Parameters

array	$x
array	$n
int	$mode

Returns

array

Definition at line 1963 of file BigInteger.php.

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

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

    {
        if ($mode == self::MONTGOMERY) {
            return $this->_montgomeryMultiply($x, $x, $n);
        }
        return $this->_reduce($this->_square($x), $n, $mode);
    }

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 private

Definition at line 1022 of file BigInteger.php.

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

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().

    {
        $x_size = count($x_value);
        $y_size = count($y_value);

        if ($x_size == 0) {
            return array(
                self::VALUE => $y_value,
                self::SIGN => !$y_negative
            );
        } elseif ($y_size == 0) {
            return array(
                self::VALUE => $x_value,
                self::SIGN => $x_negative
            );
        }

        // add, if appropriate (ie. -$x - +$y or +$x - -$y)
        if ($x_negative != $y_negative) {
            $temp = $this->_add($x_value, false, $y_value, false);
            $temp[self::SIGN] = $x_negative;

            return $temp;
        }

        $diff = $this->_compare($x_value, $x_negative, $y_value, $y_negative);

        if (!$diff) {
            return array(
                self::VALUE => array(),
                self::SIGN => false
            );
        }

        // switch $x and $y around, if appropriate.
        if ((!$x_negative && $diff < 0) || ($x_negative && $diff > 0)) {
            $temp = $x_value;
            $x_value = $y_value;
            $y_value = $temp;

            $x_negative = !$x_negative;

            $x_size = count($x_value);
            $y_size = count($y_value);
        }

        // at this point, $x_value should be at least as big as - if not bigger than - $y_value

        $carry = 0;
        for ($i = 0, $j = 1; $j < $y_size; $i+=2, $j+=2) {
            $sum = $x_value[$j] * self::$baseFull + $x_value[$i] - $y_value[$j] * self::$baseFull - $y_value[$i] - $carry;
            $carry = $sum < 0; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1
            $sum = $carry ? $sum + self::$maxDigit2 : $sum;

            $temp = self::$base === 26 ? intval($sum / 0x4000000) : ($sum >> 31);

            $x_value[$i] = (int) ($sum - self::$baseFull * $temp);
            $x_value[$j] = $temp;
        }

        if ($j == $y_size) { // ie. if $y_size is odd
            $sum = $x_value[$i] - $y_value[$i] - $carry;
            $carry = $sum < 0;
            $x_value[$i] = $carry ? $sum + self::$baseFull : $sum;
            ++$i;
        }

        if ($carry) {
            for (; !$x_value[$i]; ++$i) {
                $x_value[$i] = self::$maxDigit;
            }
            --$x_value[$i];
        }

        return array(
            self::VALUE => $this->_trim($x_value),
            self::SIGN => $x_negative
        );
    }

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

private

Definition at line 3589 of file BigInteger.php.

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().

    {
        for ($i = count($value) - 1; $i >= 0; --$i) {
            if ($value[$i]) {
                break;
            }
            unset($value[$i]);
        }

        return $value;
    }

Here is the caller graph for this function:

abs()

phpseclib\Math\BigInteger::abs

(

)

Absolute value.

Returns

public

Definition at line 2642 of file BigInteger.php.

References phpseclib\Math\BigInteger\$value.

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

    {
        $temp = new static();

        switch (MATH_BIGINTEGER_MODE) {
            case self::MODE_GMP:
                $temp->value = gmp_abs($this->value);
                break;
            case self::MODE_BCMATH:
                $temp->value = (bccomp($this->value, '0', 0) < 0) ? substr($this->value, 1) : $this->value;
                break;
            default:
                $temp->value = $this->value;
        }

        return $temp;
    }

Here is the caller graph for this function:

add()

phpseclib\Math\BigInteger::add

(

$y

)

Adds two BigIntegers.

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

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

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

Parameters

\phpseclib\Math\BigInteger

$y

Returns

public

Definition at line 859 of file BigInteger.php.

References $result, $y, phpseclib\Math\BigInteger\_add(), and phpseclib\Math\BigInteger\_normalize().

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

    {
        switch (MATH_BIGINTEGER_MODE) {
            case self::MODE_GMP:
                $temp = new static();
                $temp->value = gmp_add($this->value, $y->value);

                return $this->_normalize($temp);
            case self::MODE_BCMATH:
                $temp = new static();
                $temp->value = bcadd($this->value, $y->value, 0);

                return $this->_normalize($temp);
        }

        $temp = $this->_add($this->value, $this->is_negative, $y->value, $y->is_negative);

        $result = new static();
        $result->value = $temp[self::VALUE];
        $result->is_negative = $temp[self::SIGN];

        return $this->_normalize($result);
    }

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

public

Definition at line 2776 of file BigInteger.php.

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

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

    {
        switch (MATH_BIGINTEGER_MODE) {
            case self::MODE_GMP:
                $temp = new static();
                $temp->value = gmp_and($this->value, $x->value);

                return $this->_normalize($temp);
            case self::MODE_BCMATH:
                $left = $this->toBytes();
                $right = $x->toBytes();

                $length = max(strlen($left), strlen($right));

                $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
                $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);

                return $this->_normalize(new static($left & $right, 256));
        }

        $result = $this->copy();

        $length = min(count($x->value), count($this->value));

        $result->value = array_slice($result->value, 0, $length);

        for ($i = 0; $i < $length; ++$i) {
            $result->value[$i]&= $x->value[$i];
        }

        return $this->_normalize($result);
    }

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

public

Definition at line 3013 of file BigInteger.php.

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().

    {
        $bits = $this->toBytes();

        if ($this->precision > 0) {
            $precision = $this->precision;
            if (MATH_BIGINTEGER_MODE == self::MODE_BCMATH) {
                $mask = $this->bitmask->subtract(new static(1));
                $mask = $mask->toBytes();
            } else {
                $mask = $this->bitmask->toBytes();
            }
        } else {
            $temp = ord($bits[0]);
            for ($i = 0; $temp >> $i; ++$i) {
            }
            $precision = 8 * strlen($bits) - 8 + $i;
            $mask = chr((1 << ($precision & 0x7)) - 1) . str_repeat(chr(0xFF), $precision >> 3);
        }

        if ($shift < 0) {
            $shift+= $precision;
        }
        $shift%= $precision;

        if (!$shift) {
            return $this->copy();
        }

        $left = $this->bitwise_leftShift($shift);
        $left = $left->bitwise_and(new static($mask, 256));
        $right = $this->bitwise_rightShift($precision - $shift);
        $result = MATH_BIGINTEGER_MODE != self::MODE_BCMATH ? $left->bitwise_or($right) : $left->add($right);
        return $this->_normalize($result);
    }

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

public

Definition at line 2976 of file BigInteger.php.

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

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

    {
        $temp = new static();

        switch (MATH_BIGINTEGER_MODE) {
            case self::MODE_GMP:
                static $two;

                if (!isset($two)) {
                    $two = gmp_init('2');
                }

                $temp->value = gmp_mul($this->value, gmp_pow($two, $shift));

                break;
            case self::MODE_BCMATH:
                $temp->value = bcmul($this->value, bcpow('2', $shift, 0), 0);

                break;
            default: // could just replace _rshift with this, but then all _lshift() calls would need to be rewritten
                     // and I don't want to do that...
                $temp->value = $this->value;
                $temp->_lshift($shift);
        }

        return $this->_normalize($temp);
    }

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.

public

Definition at line 2896 of file BigInteger.php.

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

    {
        // calculuate "not" without regard to $this->precision
        // (will always result in a smaller number.  ie. ~1 isn't 1111 1110 - it's 0)
        $temp = $this->toBytes();
        if ($temp == '') {
            return '';
        }
        $pre_msb = decbin(ord($temp[0]));
        $temp = ~$temp;
        $msb = decbin(ord($temp[0]));
        if (strlen($msb) == 8) {
            $msb = substr($msb, strpos($msb, '0'));
        }
        $temp[0] = chr(bindec($msb));

        // see if we need to add extra leading 1's
        $current_bits = strlen($pre_msb) + 8 * strlen($temp) - 8;
        $new_bits = $this->precision - $current_bits;
        if ($new_bits <= 0) {
            return $this->_normalize(new static($temp, 256));
        }

        // generate as many leading 1's as we need to.
        $leading_ones = chr((1 << ($new_bits & 0x7)) - 1) . str_repeat(chr(0xFF), $new_bits >> 3);
        $this->_base256_lshift($leading_ones, $current_bits);

        $temp = str_pad($temp, strlen($leading_ones), chr(0), STR_PAD_LEFT);

        return $this->_normalize(new static($leading_ones | $temp, 256));
    }

Here is the call graph for this function:

bitwise_or()

phpseclib\Math\BigInteger::bitwise_or

(

$x

)

Logical Or.

Parameters

\phpseclib\Math\BigInteger

$x

public

Definition at line 2817 of file BigInteger.php.

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

    {
        switch (MATH_BIGINTEGER_MODE) {
            case self::MODE_GMP:
                $temp = new static();
                $temp->value = gmp_or($this->value, $x->value);

                return $this->_normalize($temp);
            case self::MODE_BCMATH:
                $left = $this->toBytes();
                $right = $x->toBytes();

                $length = max(strlen($left), strlen($right));

                $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
                $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);

                return $this->_normalize(new static($left | $right, 256));
        }

        $length = max(count($this->value), count($x->value));
        $result = $this->copy();
        $result->value = array_pad($result->value, $length, 0);
        $x->value = array_pad($x->value, $length, 0);

        for ($i = 0; $i < $length; ++$i) {
            $result->value[$i]|= $x->value[$i];
        }

        return $this->_normalize($result);
    }

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

public

Definition at line 3058 of file BigInteger.php.

References phpseclib\Math\BigInteger\bitwise_leftRotate().

    {
        return $this->bitwise_leftRotate(-$shift);
    }

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

public

Definition at line 2938 of file BigInteger.php.

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

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

    {
        $temp = new static();

        switch (MATH_BIGINTEGER_MODE) {
            case self::MODE_GMP:
                static $two;

                if (!isset($two)) {
                    $two = gmp_init('2');
                }

                $temp->value = gmp_div_q($this->value, gmp_pow($two, $shift));

                break;
            case self::MODE_BCMATH:
                $temp->value = bcdiv($this->value, bcpow('2', $shift, 0), 0);

                break;
            default: // could just replace _lshift with this, but then all _lshift() calls would need to be rewritten
                     // and I don't want to do that...
                $temp->value = $this->value;
                $temp->_rshift($shift);
        }

        return $this->_normalize($temp);
    }

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

public

Definition at line 2857 of file BigInteger.php.

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

    {
        switch (MATH_BIGINTEGER_MODE) {
            case self::MODE_GMP:
                $temp = new static();
                $temp->value = gmp_xor($this->value, $x->value);

                return $this->_normalize($temp);
            case self::MODE_BCMATH:
                $left = $this->toBytes();
                $right = $x->toBytes();

                $length = max(strlen($left), strlen($right));

                $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
                $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);

                return $this->_normalize(new static($left ^ $right, 256));
        }

        $length = max(count($this->value), count($x->value));
        $result = $this->copy();
        $result->value = array_pad($result->value, $length, 0);
        $x->value = array_pad($x->value, $length, 0);

        for ($i = 0; $i < $length; ++$i) {
            $result->value[$i]^= $x->value[$i];
        }

        return $this->_normalize($result);
    }

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. public

See also

self::equals()

Definition at line 2678 of file BigInteger.php.

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

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

    {
        switch (MATH_BIGINTEGER_MODE) {
            case self::MODE_GMP:
                return gmp_cmp($this->value, $y->value);
            case self::MODE_BCMATH:
                return bccomp($this->value, $y->value, 0);
        }

        return $this->_compare($this->value, $this->is_negative, $y->value, $y->is_negative);
    }

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

public

See also

self::__clone()

Returns

Definition at line 728 of file BigInteger.php.

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().

    {
        $temp = new static();
        $temp->value = $this->value;
        $temp->is_negative = $this->is_negative;
        $temp->precision = $this->precision;
        $temp->bitmask = $this->bitmask;
        return $temp;
    }

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 ('10'); $b = new ('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 public

Definition at line 1406 of file BigInteger.php.

References $i, 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(), and phpseclib\Math\BigInteger\copy().

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

    {
        switch (MATH_BIGINTEGER_MODE) {
            case self::MODE_GMP:
                $quotient = new static();
                $remainder = new static();

                list($quotient->value, $remainder->value) = gmp_div_qr($this->value, $y->value);

                if (gmp_sign($remainder->value) < 0) {
                    $remainder->value = gmp_add($remainder->value, gmp_abs($y->value));
                }

                return array($this->_normalize($quotient), $this->_normalize($remainder));
            case self::MODE_BCMATH:
                $quotient = new static();
                $remainder = new static();

                $quotient->value = bcdiv($this->value, $y->value, 0);
                $remainder->value = bcmod($this->value, $y->value);

                if ($remainder->value[0] == '-') {
                    $remainder->value = bcadd($remainder->value, $y->value[0] == '-' ? substr($y->value, 1) : $y->value, 0);
                }

                return array($this->_normalize($quotient), $this->_normalize($remainder));
        }

        if (count($y->value) == 1) {
            list($q, $r) = $this->_divide_digit($this->value, $y->value[0]);
            $quotient = new static();
            $remainder = new static();
            $quotient->value = $q;
            $remainder->value = array($r);
            $quotient->is_negative = $this->is_negative != $y->is_negative;
            return array($this->_normalize($quotient), $this->_normalize($remainder));
        }

        static $zero;
        if (!isset($zero)) {
            $zero = new static();
        }

        $x = $this->copy();
        $y = $y->copy();

        $x_sign = $x->is_negative;
        $y_sign = $y->is_negative;

        $x->is_negative = $y->is_negative = false;

        $diff = $x->compare($y);

        if (!$diff) {
            $temp = new static();
            $temp->value = array(1);
            $temp->is_negative = $x_sign != $y_sign;
            return array($this->_normalize($temp), $this->_normalize(new static()));
        }

        if ($diff < 0) {
            // if $x is negative, "add" $y.
            if ($x_sign) {
                $x = $y->subtract($x);
            }
            return array($this->_normalize(new static()), $this->_normalize($x));
        }

        // normalize $x and $y as described in HAC 14.23 / 14.24
        $msb = $y->value[count($y->value) - 1];
        for ($shift = 0; !($msb & self::$msb); ++$shift) {
            $msb <<= 1;
        }
        $x->_lshift($shift);
        $y->_lshift($shift);
        $y_value = &$y->value;

        $x_max = count($x->value) - 1;
        $y_max = count($y->value) - 1;

        $quotient = new static();
        $quotient_value = &$quotient->value;
        $quotient_value = $this->_array_repeat(0, $x_max - $y_max + 1);

        static $temp, $lhs, $rhs;
        if (!isset($temp)) {
            $temp = new static();
            $lhs =  new static();
            $rhs =  new static();
        }
        $temp_value = &$temp->value;
        $rhs_value =  &$rhs->value;

        // $temp = $y << ($x_max - $y_max-1) in base 2**26
        $temp_value = array_merge($this->_array_repeat(0, $x_max - $y_max), $y_value);

        while ($x->compare($temp) >= 0) {
            // calculate the "common residue"
            ++$quotient_value[$x_max - $y_max];
            $x = $x->subtract($temp);
            $x_max = count($x->value) - 1;
        }

        for ($i = $x_max; $i >= $y_max + 1; --$i) {
            $x_value = &$x->value;
            $x_window = array(
                isset($x_value[$i]) ? $x_value[$i] : 0,
                isset($x_value[$i - 1]) ? $x_value[$i - 1] : 0,
                isset($x_value[$i - 2]) ? $x_value[$i - 2] : 0
            );
            $y_window = array(
                $y_value[$y_max],
                ($y_max > 0) ? $y_value[$y_max - 1] : 0
            );

            $q_index = $i - $y_max - 1;
            if ($x_window[0] == $y_window[0]) {
                $quotient_value[$q_index] = self::$maxDigit;
            } else {
                $quotient_value[$q_index] = $this->_safe_divide(
                    $x_window[0] * self::$baseFull + $x_window[1],
                    $y_window[0]
                );
            }

            $temp_value = array($y_window[1], $y_window[0]);

            $lhs->value = array($quotient_value[$q_index]);
            $lhs = $lhs->multiply($temp);

            $rhs_value = array($x_window[2], $x_window[1], $x_window[0]);

            while ($lhs->compare($rhs) > 0) {
                --$quotient_value[$q_index];

                $lhs->value = array($quotient_value[$q_index]);
                $lhs = $lhs->multiply($temp);
            }

            $adjust = $this->_array_repeat(0, $q_index);
            $temp_value = array($quotient_value[$q_index]);
            $temp = $temp->multiply($y);
            $temp_value = &$temp->value;
            $temp_value = array_merge($adjust, $temp_value);

            $x = $x->subtract($temp);

            if ($x->compare($zero) < 0) {
                $temp_value = array_merge($adjust, $y_value);
                $x = $x->add($temp);

                --$quotient_value[$q_index];
            }

            $x_max = count($x_value) - 1;
        }

        // unnormalize the remainder
        $x->_rshift($shift);

        $quotient->is_negative = $x_sign != $y_sign;

        // calculate the "common residue", if appropriate
        if ($x_sign) {
            $y->_rshift($shift);
            $x = $y->subtract($x);
        }

        return array($this->_normalize($quotient), $this->_normalize($x));
    }

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 public

See also

self::compare()

Definition at line 2736 of file BigInteger.php.

References $x.

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

    {
        switch (MATH_BIGINTEGER_MODE) {
            case self::MODE_GMP:
                return gmp_cmp($this->value, $x->value) == 0;
            default:
                return $this->value === $x->value && $this->is_negative == $x->is_negative;
        }
    }

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 (693); $b = new (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

public

Definition at line 2501 of file BigInteger.php.

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

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

    {
        switch (MATH_BIGINTEGER_MODE) {
            case self::MODE_GMP:
                extract(gmp_gcdext($this->value, $n->value));

                return array(
                    'gcd' => $this->_normalize(new static($g)),
                    'x'   => $this->_normalize(new static($s)),
                    'y'   => $this->_normalize(new static($t))
                );
            case self::MODE_BCMATH:
                // it might be faster to use the binary xGCD algorithim here, as well, but (1) that algorithim works
                // best when the base is a power of 2 and (2) i don't think it'd make much difference, anyway.  as is,
                // the basic extended euclidean algorithim is what we're using.

                $u = $this->value;
                $v = $n->value;

                $a = '1';
                $b = '0';
                $c = '0';
                $d = '1';

                while (bccomp($v, '0', 0) != 0) {
                    $q = bcdiv($u, $v, 0);

                    $temp = $u;
                    $u = $v;
                    $v = bcsub($temp, bcmul($v, $q, 0), 0);

                    $temp = $a;
                    $a = $c;
                    $c = bcsub($temp, bcmul($a, $q, 0), 0);

                    $temp = $b;
                    $b = $d;
                    $d = bcsub($temp, bcmul($b, $q, 0), 0);
                }

                return array(
                    'gcd' => $this->_normalize(new static($u)),
                    'x'   => $this->_normalize(new static($a)),
                    'y'   => $this->_normalize(new static($b))
                );
        }

        $y = $n->copy();
        $x = $this->copy();
        $g = new static();
        $g->value = array(1);

        while (!(($x->value[0] & 1)|| ($y->value[0] & 1))) {
            $x->_rshift(1);
            $y->_rshift(1);
            $g->_lshift(1);
        }

        $u = $x->copy();
        $v = $y->copy();

        $a = new static();
        $b = new static();
        $c = new static();
        $d = new static();

        $a->value = $d->value = $g->value = array(1);
        $b->value = $c->value = array();

        while (!empty($u->value)) {
            while (!($u->value[0] & 1)) {
                $u->_rshift(1);
                if ((!empty($a->value) && ($a->value[0] & 1)) || (!empty($b->value) && ($b->value[0] & 1))) {
                    $a = $a->add($y);
                    $b = $b->subtract($x);
                }
                $a->_rshift(1);
                $b->_rshift(1);
            }

            while (!($v->value[0] & 1)) {
                $v->_rshift(1);
                if ((!empty($d->value) && ($d->value[0] & 1)) || (!empty($c->value) && ($c->value[0] & 1))) {
                    $c = $c->add($y);
                    $d = $d->subtract($x);
                }
                $c->_rshift(1);
                $d->_rshift(1);
            }

            if ($u->compare($v) >= 0) {
                $u = $u->subtract($v);
                $a = $a->subtract($c);
                $b = $b->subtract($d);
            } else {
                $v = $v->subtract($u);
                $c = $c->subtract($a);
                $d = $d->subtract($b);
            }
        }

        return array(
            'gcd' => $this->_normalize($g->multiply($v)),
            'x'   => $this->_normalize($c),
            'y'   => $this->_normalize($d)
        );
    }

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 (693); $b = new (609);

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

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

Parameters

\phpseclib\Math\BigInteger

$n

Returns

public

Definition at line 2630 of file BigInteger.php.

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

    {
        extract($this->extendedGCD($n));
        return $gcd;
    }

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 public

Definition at line 3320 of file BigInteger.php.

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\random(), and phpseclib\Math\BigInteger\toBytes().

    {
        $length = strlen($this->toBytes());

        if (!$t) {
            // see HAC 4.49 "Note (controlling the error probability)"
            // @codingStandardsIgnoreStart
                 if ($length >= 163) { $t =  2; } // floor(1300 / 8)
            else if ($length >= 106) { $t =  3; } // floor( 850 / 8)
            else if ($length >= 81 ) { $t =  4; } // floor( 650 / 8)
            else if ($length >= 68 ) { $t =  5; } // floor( 550 / 8)
            else if ($length >= 56 ) { $t =  6; } // floor( 450 / 8)
            else if ($length >= 50 ) { $t =  7; } // floor( 400 / 8)
            else if ($length >= 43 ) { $t =  8; } // floor( 350 / 8)
            else if ($length >= 37 ) { $t =  9; } // floor( 300 / 8)
            else if ($length >= 31 ) { $t = 12; } // floor( 250 / 8)
            else if ($length >= 25 ) { $t = 15; } // floor( 200 / 8)
            else if ($length >= 18 ) { $t = 18; } // floor( 150 / 8)
            else                     { $t = 27; }
            // @codingStandardsIgnoreEnd
        }

        // ie. gmp_testbit($this, 0)
        // ie. isEven() or !isOdd()
        switch (MATH_BIGINTEGER_MODE) {
            case self::MODE_GMP:
                return gmp_prob_prime($this->value, $t) != 0;
            case self::MODE_BCMATH:
                if ($this->value === '2') {
                    return true;
                }
                if ($this->value[strlen($this->value) - 1] % 2 == 0) {
                    return false;
                }
                break;
            default:
                if ($this->value == array(2)) {
                    return true;
                }
                if (~$this->value[0] & 1) {
                    return false;
                }
        }

        static $primes, $zero, $one, $two;

        if (!isset($primes)) {
            $primes = array(
                3,    5,    7,    11,   13,   17,   19,   23,   29,   31,   37,   41,   43,   47,   53,   59,
                61,   67,   71,   73,   79,   83,   89,   97,   101,  103,  107,  109,  113,  127,  131,  137,
                139,  149,  151,  157,  163,  167,  173,  179,  181,  191,  193,  197,  199,  211,  223,  227,
                229,  233,  239,  241,  251,  257,  263,  269,  271,  277,  281,  283,  293,  307,  311,  313,
                317,  331,  337,  347,  349,  353,  359,  367,  373,  379,  383,  389,  397,  401,  409,  419,
                421,  431,  433,  439,  443,  449,  457,  461,  463,  467,  479,  487,  491,  499,  503,  509,
                521,  523,  541,  547,  557,  563,  569,  571,  577,  587,  593,  599,  601,  607,  613,  617,
                619,  631,  641,  643,  647,  653,  659,  661,  673,  677,  683,  691,  701,  709,  719,  727,
                733,  739,  743,  751,  757,  761,  769,  773,  787,  797,  809,  811,  821,  823,  827,  829,
                839,  853,  857,  859,  863,  877,  881,  883,  887,  907,  911,  919,  929,  937,  941,  947,
                953,  967,  971,  977,  983,  991,  997
            );

            if (MATH_BIGINTEGER_MODE != self::MODE_INTERNAL) {
                for ($i = 0; $i < count($primes); ++$i) {
                    $primes[$i] = new static($primes[$i]);
                }
            }

            $zero = new static();
            $one = new static(1);
            $two = new static(2);
        }

        if ($this->equals($one)) {
            return false;
        }

        // see HAC 4.4.1 "Random search for probable primes"
        if (MATH_BIGINTEGER_MODE != self::MODE_INTERNAL) {
            foreach ($primes as $prime) {
                list(, $r) = $this->divide($prime);
                if ($r->equals($zero)) {
                    return $this->equals($prime);
                }
            }
        } else {
            $value = $this->value;
            foreach ($primes as $prime) {
                list(, $r) = $this->_divide_digit($value, $prime);
                if (!$r) {
                    return count($value) == 1 && $value[0] == $prime;
                }
            }
        }

        $n   = $this->copy();
        $n_1 = $n->subtract($one);
        $n_2 = $n->subtract($two);

        $r = $n_1->copy();
        $r_value = $r->value;
        // ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s));
        if (MATH_BIGINTEGER_MODE == self::MODE_BCMATH) {
            $s = 0;
            // if $n was 1, $r would be 0 and this would be an infinite loop, hence our $this->equals($one) check earlier
            while ($r->value[strlen($r->value) - 1] % 2 == 0) {
                $r->value = bcdiv($r->value, '2', 0);
                ++$s;
            }
        } else {
            for ($i = 0, $r_length = count($r_value); $i < $r_length; ++$i) {
                $temp = ~$r_value[$i] & 0xFFFFFF;
                for ($j = 1; ($temp >> $j) & 1; ++$j) {
                }
                if ($j != 25) {
                    break;
                }
            }
            $s = 26 * $i + $j - 1;
            $r->_rshift($s);
        }

        for ($i = 0; $i < $t; ++$i) {
            $a = $this->random($two, $n_2);
            $y = $a->modPow($r, $n);

            if (!$y->equals($one) && !$y->equals($n_1)) {
                for ($j = 1; $j < $s && !$y->equals($n_1); ++$j) {
                    $y = $y->modPow($two, $n);
                    if ($y->equals($one)) {
                        return false;
                    }
                }

                if (!$y->equals($n_1)) {
                    return false;
                }
            }
        }
        return true;
    }

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 (30); $b = new (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

|false public

Definition at line 2437 of file BigInteger.php.

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

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

    {
        switch (MATH_BIGINTEGER_MODE) {
            case self::MODE_GMP:
                $temp = new static();
                $temp->value = gmp_invert($this->value, $n->value);

                return ($temp->value === false) ? false : $this->_normalize($temp);
        }

        static $zero, $one;
        if (!isset($zero)) {
            $zero = new static();
            $one = new static(1);
        }

        // $x mod -$n == $x mod $n.
        $n = $n->abs();

        if ($this->compare($zero) < 0) {
            $temp = $this->abs();
            $temp = $temp->modInverse($n);
            return $this->_normalize($n->subtract($temp));
        }

        extract($this->extendedGCD($n));

        if (!$gcd->equals($one)) {
            return false;
        }

        $x = $x->compare($zero) < 0 ? $x->add($n) : $x;

        return $this->compare($zero) < 0 ? $this->_normalize($n->subtract($x)) : $this->_normalize($x);
    }

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 ('10'); $b = new ('20'); $c = new ('30');

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

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

Parameters

\phpseclib\Math\BigInteger	$e
\phpseclib\Math\BigInteger	$n

Returns

public

Definition at line 1641 of file BigInteger.php.

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().

    {
        $n = $this->bitmask !== false && $this->bitmask->compare($n) < 0 ? $this->bitmask : $n->abs();

        if ($e->compare(new static()) < 0) {
            $e = $e->abs();

            $temp = $this->modInverse($n);
            if ($temp === false) {
                return false;
            }

            return $this->_normalize($temp->modPow($e, $n));
        }

        if (MATH_BIGINTEGER_MODE == self::MODE_GMP) {
            $temp = new static();
            $temp->value = gmp_powm($this->value, $e->value, $n->value);

            return $this->_normalize($temp);
        }

        if ($this->compare(new static()) < 0 || $this->compare($n) > 0) {
            list(, $temp) = $this->divide($n);
            return $temp->modPow($e, $n);
        }

        if (defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) {
            $components = array(
                'modulus' => $n->toBytes(true),
                'publicExponent' => $e->toBytes(true)
            );

            $components = array(
                'modulus' => pack('Ca*a*', 2, $this->_encodeASN1Length(strlen($components['modulus'])), $components['modulus']),
                'publicExponent' => pack('Ca*a*', 2, $this->_encodeASN1Length(strlen($components['publicExponent'])), $components['publicExponent'])
            );

            $RSAPublicKey = pack(
                'Ca*a*a*',
                48,
                $this->_encodeASN1Length(strlen($components['modulus']) + strlen($components['publicExponent'])),
                $components['modulus'],
                $components['publicExponent']
            );

            $rsaOID = pack('H*', '300d06092a864886f70d0101010500'); // hex version of MA0GCSqGSIb3DQEBAQUA
            $RSAPublicKey = chr(0) . $RSAPublicKey;
            $RSAPublicKey = chr(3) . $this->_encodeASN1Length(strlen($RSAPublicKey)) . $RSAPublicKey;

            $encapsulated = pack(
                'Ca*a*',
                48,
                $this->_encodeASN1Length(strlen($rsaOID . $RSAPublicKey)),
                $rsaOID . $RSAPublicKey
            );

            $RSAPublicKey = "-----BEGIN PUBLIC KEY-----\r\n" .
                             chunk_split(base64_encode($encapsulated)) .
                             '-----END PUBLIC KEY-----';

            $plaintext = str_pad($this->toBytes(), strlen($n->toBytes(true)) - 1, "\0", STR_PAD_LEFT);

            if (openssl_public_encrypt($plaintext, $result, $RSAPublicKey, OPENSSL_NO_PADDING)) {
                return new static($result, 256);
            }
        }

        if (MATH_BIGINTEGER_MODE == self::MODE_BCMATH) {
            $temp = new static();
            $temp->value = bcpowmod($this->value, $e->value, $n->value, 0);

            return $this->_normalize($temp);
        }

        if (empty($e->value)) {
            $temp = new static();
            $temp->value = array(1);
            return $this->_normalize($temp);
        }

        if ($e->value == array(1)) {
            list(, $temp) = $this->divide($n);
            return $this->_normalize($temp);
        }

        if ($e->value == array(2)) {
            $temp = new static();
            $temp->value = $this->_square($this->value);
            list(, $temp) = $temp->divide($n);
            return $this->_normalize($temp);
        }

        return $this->_normalize($this->_slidingWindow($e, $n, self::BARRETT));

        // the following code, although not callable, can be run independently of the above code
        // although the above code performed better in my benchmarks the following could might
        // perform better under different circumstances. in lieu of deleting it it's just been
        // made uncallable

        // is the modulo odd?
        if ($n->value[0] & 1) {
            return $this->_normalize($this->_slidingWindow($e, $n, self::MONTGOMERY));
        }
        // if it's not, it's even

        // find the lowest set bit (eg. the max pow of 2 that divides $n)
        for ($i = 0; $i < count($n->value); ++$i) {
            if ($n->value[$i]) {
                $temp = decbin($n->value[$i]);
                $j = strlen($temp) - strrpos($temp, '1') - 1;
                $j+= 26 * $i;
                break;
            }
        }
        // at this point, 2^$j * $n/(2^$j) == $n

        $mod1 = $n->copy();
        $mod1->_rshift($j);
        $mod2 = new static();
        $mod2->value = array(1);
        $mod2->_lshift($j);

        $part1 = ($mod1->value != array(1)) ? $this->_slidingWindow($e, $mod1, self::MONTGOMERY) : new static();
        $part2 = $this->_slidingWindow($e, $mod2, self::POWEROF2);

        $y1 = $mod2->modInverse($mod1);
        $y2 = $mod1->modInverse($mod2);

        $result = $part1->multiply($mod2);
        $result = $result->multiply($y1);

        $temp = $part2->multiply($mod1);
        $temp = $temp->multiply($y2);

        $result = $result->add($temp);
        list(, $result) = $result->divide($n);

        return $this->_normalize($result);
    }

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 ('10'); $b = new ('20');

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

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

Parameters

\phpseclib\Math\BigInteger

$x

Returns

public

Definition at line 1121 of file BigInteger.php.

References $x, phpseclib\Math\BigInteger\_multiply(), and phpseclib\Math\BigInteger\_normalize().

    {
        switch (MATH_BIGINTEGER_MODE) {
            case self::MODE_GMP:
                $temp = new static();
                $temp->value = gmp_mul($this->value, $x->value);

                return $this->_normalize($temp);
            case self::MODE_BCMATH:
                $temp = new static();
                $temp->value = bcmul($this->value, $x->value, 0);

                return $this->_normalize($temp);
        }

        $temp = $this->_multiply($this->value, $this->is_negative, $x->value, $x->is_negative);

        $product = new static();
        $product->value = $temp[self::VALUE];
        $product->is_negative = $temp[self::SIGN];

        return $this->_normalize($product);
    }

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

public

Definition at line 1792 of file BigInteger.php.

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

    {
        return $this->modPow($e, $n);
    }

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

public

Definition at line 3109 of file BigInteger.php.

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

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

    {
        if ($arg1 === false) {
            return false;
        }

        if ($arg2 === false) {
            $max = $arg1;
            $min = $this;
        } else {
            $min = $arg1;
            $max = $arg2;
        }

        $compare = $max->compare($min);

        if (!$compare) {
            return $this->_normalize($min);
        } elseif ($compare < 0) {
            // if $min is bigger then $max, swap $min and $max
            $temp = $max;
            $max = $min;
            $min = $temp;
        }

        static $one;
        if (!isset($one)) {
            $one = new static(1);
        }

        $max = $max->subtract($min->subtract($one));
        $size = strlen(ltrim($max->toBytes(), chr(0)));

        /*
            doing $random % $max doesn't work because some numbers will be more likely to occur than others.
            eg. if $max is 140 and $random's max is 255 then that'd mean both $random = 5 and $random = 145
            would produce 5 whereas the only value of random that could produce 139 would be 139. ie.
            not all numbers would be equally likely. some would be more likely than others.

            creating a whole new random number until you find one that is within the range doesn't work
            because, for sufficiently small ranges, the likelihood that you'd get a number within that range
            would be pretty small. eg. with $random's max being 255 and if your $max being 1 the probability
            would be pretty high that $random would be greater than $max.

            phpseclib works around this using the technique described here:

            http://crypto.stackexchange.com/questions/5708/creating-a-small-number-from-a-cryptographically-secure-random-string
        */
        $random_max = new static(chr(1) . str_repeat("\0", $size), 256);
        $random = $this->_random_number_helper($size);

        list($max_multiple) = $random_max->divide($max);
        $max_multiple = $max_multiple->multiply($max);

        while ($random->compare($max_multiple) >= 0) {
            $random = $random->subtract($max_multiple);
            $random_max = $random_max->subtract($max_multiple);
            $random = $random->bitwise_leftShift(8);
            $random = $random->add($this->_random_number_helper(1));
            $random_max = $random_max->bitwise_leftShift(8);
            list($max_multiple) = $random_max->divide($max);
            $max_multiple = $max_multiple->multiply($max);
        }
        list(, $random) = $random->divide($max);

        return $this->_normalize($random->add($min));
    }

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 public

Definition at line 3190 of file BigInteger.php.

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

    {
        if ($arg1 === false) {
            return false;
        }

        if ($arg2 === false) {
            $max = $arg1;
            $min = $this;
        } else {
            $min = $arg1;
            $max = $arg2;
        }

        $compare = $max->compare($min);

        if (!$compare) {
            return $min->isPrime() ? $min : false;
        } elseif ($compare < 0) {
            // if $min is bigger then $max, swap $min and $max
            $temp = $max;
            $max = $min;
            $min = $temp;
        }

        static $one, $two;
        if (!isset($one)) {
            $one = new static(1);
            $two = new static(2);
        }

        $start = time();

        $x = $this->random($min, $max);

        // gmp_nextprime() requires PHP 5 >= 5.2.0 per <http://php.net/gmp-nextprime>.
        if (MATH_BIGINTEGER_MODE == self::MODE_GMP && extension_loaded('gmp')) {
            $p = new static();
            $p->value = gmp_nextprime($x->value);

            if ($p->compare($max) <= 0) {
                return $p;
            }

            if (!$min->equals($x)) {
                $x = $x->subtract($one);
            }

            return $x->randomPrime($min, $x);
        }

        if ($x->equals($two)) {
            return $x;
        }

        $x->_make_odd();
        if ($x->compare($max) > 0) {
            // if $x > $max then $max is even and if $min == $max then no prime number exists between the specified range
            if ($min->equals($max)) {
                return false;
            }
            $x = $min->copy();
            $x->_make_odd();
        }

        $initial_x = $x->copy();

        while (true) {
            if ($timeout !== false && time() - $start > $timeout) {
                return false;
            }

            if ($x->isPrime()) {
                return $x;
            }

            $x = $x->add($two);

            if ($x->compare($max) > 0) {
                $x = $min->copy();
                if ($x->equals($two)) {
                    return $x;
                }
                $x->_make_odd();
            }

            if ($x->equals($initial_x)) {
                return false;
            }
        }
    }

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

public

Definition at line 2755 of file BigInteger.php.

References phpseclib\Math\BigInteger\_normalize().

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

    {
        $this->precision = $bits;
        if (MATH_BIGINTEGER_MODE != self::MODE_BCMATH) {
            $this->bitmask = new static(chr((1 << ($bits & 0x7)) - 1) . str_repeat(chr(0xFF), $bits >> 3), 256);
        } else {
            $this->bitmask = new static(bcpow('2', $bits, 0));
        }

        $temp = $this->_normalize($this);
        $this->value = $temp->value;
    }

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 ('10'); $b = new ('20');

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

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

Parameters

\phpseclib\Math\BigInteger

$y

Returns

public

Definition at line 988 of file BigInteger.php.

References $result, $y, phpseclib\Math\BigInteger\_normalize(), and phpseclib\Math\BigInteger\_subtract().

    {
        switch (MATH_BIGINTEGER_MODE) {
            case self::MODE_GMP:
                $temp = new static();
                $temp->value = gmp_sub($this->value, $y->value);

                return $this->_normalize($temp);
            case self::MODE_BCMATH:
                $temp = new static();
                $temp->value = bcsub($this->value, $y->value, 0);

                return $this->_normalize($temp);
        }

        $temp = $this->_subtract($this->value, $this->is_negative, $y->value, $y->is_negative);

        $result = new static();
        $result->value = $temp[self::VALUE];
        $result->is_negative = $temp[self::SIGN];

        return $this->_normalize($result);
    }

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 ('65');

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

Parameters

bool

$twos_compliment

Returns

string public

Definition at line 642 of file BigInteger.php.

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

    {
        $hex = $this->toHex($twos_compliment);
        $bits = '';
        for ($i = strlen($hex) - 8, $start = strlen($hex) & 7; $i >= $start; $i-=8) {
            $bits = str_pad(decbin(hexdec(substr($hex, $i, 8))), 32, '0', STR_PAD_LEFT) . $bits;
        }
        if ($start) { // hexdec('') == 0
            $bits = str_pad(decbin(hexdec(substr($hex, 0, $start))), 8, '0', STR_PAD_LEFT) . $bits;
        }
        $result = $this->precision > 0 ? substr($bits, -$this->precision) : ltrim($bits, '0');

        if ($twos_compliment && $this->compare(new static()) > 0 && $this->precision <= 0) {
            return '0' . $result;
        }

        return $result;
    }

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 ('65');

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

Parameters

bool

$twos_compliment

Returns

string public

Definition at line 522 of file BigInteger.php.

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

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().

    {
        if ($twos_compliment) {
            $comparison = $this->compare(new static());
            if ($comparison == 0) {
                return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
            }

            $temp = $comparison < 0 ? $this->add(new static(1)) : $this->copy();
            $bytes = $temp->toBytes();

            if (empty($bytes)) { // eg. if the number we're trying to convert is -1
                $bytes = chr(0);
            }

            if (ord($bytes[0]) & 0x80) {
                $bytes = chr(0) . $bytes;
            }

            return $comparison < 0 ? ~$bytes : $bytes;
        }

        switch (MATH_BIGINTEGER_MODE) {
            case self::MODE_GMP:
                if (gmp_cmp($this->value, gmp_init(0)) == 0) {
                    return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
                }

                $temp = gmp_strval(gmp_abs($this->value), 16);
                $temp = (strlen($temp) & 1) ? '0' . $temp : $temp;
                $temp = pack('H*', $temp);

                return $this->precision > 0 ?
                    substr(str_pad($temp, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) :
                    ltrim($temp, chr(0));
            case self::MODE_BCMATH:
                if ($this->value === '0') {
                    return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
                }

                $value = '';
                $current = $this->value;

                if ($current[0] == '-') {
                    $current = substr($current, 1);
                }

                while (bccomp($current, '0', 0) > 0) {
                    $temp = bcmod($current, '16777216');
                    $value = chr($temp >> 16) . chr($temp >> 8) . chr($temp) . $value;
                    $current = bcdiv($current, '16777216', 0);
                }

                return $this->precision > 0 ?
                    substr(str_pad($value, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) :
                    ltrim($value, chr(0));
        }

        if (!count($this->value)) {
            return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
        }
        $result = $this->_int2bytes($this->value[count($this->value) - 1]);

        $temp = $this->copy();

        for ($i = count($temp->value) - 2; $i >= 0; --$i) {
            $temp->_base256_lshift($result, self::$base);
            $result = $result | str_pad($temp->_int2bytes($temp->value[$i]), strlen($result), chr(0), STR_PAD_LEFT);
        }

        return $this->precision > 0 ?
            str_pad(substr($result, -(($this->precision + 7) >> 3)), ($this->precision + 7) >> 3, chr(0), STR_PAD_LEFT) :
            $result;
    }

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 ('65');

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

Parameters

bool

$twos_compliment

Returns

string public

Definition at line 617 of file BigInteger.php.

References phpseclib\Math\BigInteger\toBytes().

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

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

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 ('50');

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

Returns

string public

Definition at line 677 of file BigInteger.php.

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

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

    {
        switch (MATH_BIGINTEGER_MODE) {
            case self::MODE_GMP:
                return gmp_strval($this->value);
            case self::MODE_BCMATH:
                if ($this->value === '0') {
                    return '0';
                }

                return ltrim($this->value, '0');
        }

        if (!count($this->value)) {
            return '0';
        }

        $temp = $this->copy();
        $temp->is_negative = false;

        $divisor = new static();
        $divisor->value = array(self::$max10);
        $result = '';
        while (count($temp->value)) {
            list($temp, $mod) = $temp->divide($divisor);
            $result = str_pad(isset($mod->value[0]) ? $mod->value[0] : '', self::$max10Len, '0', STR_PAD_LEFT) . $result;
        }
        $result = ltrim($result, '0');
        if (empty($result)) {
            $result = '0';
        }

        if ($this->is_negative) {
            $result = '-' . $result;
        }

        return $result;
    }

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().

$baseFull

phpseclib\Math\BigInteger::$baseFull

staticprotected

Definition at line 168 of file BigInteger.php.

$bitmask

phpseclib\Math\BigInteger::$bitmask = false

Precision Bitmask.

See also

self::setPrecision() 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

Definition at line 230 of file BigInteger.php.

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

$is_negative

phpseclib\Math\BigInteger::$is_negative = false

Definition at line 200 of file BigInteger.php.

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

$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

phpseclib\Math\BigInteger::$maxDigit

staticprotected

Definition at line 169 of file BigInteger.php.

$maxDigit2

phpseclib\Math\BigInteger::$maxDigit2

staticprotected

Definition at line 183 of file BigInteger.php.

$msb

phpseclib\Math\BigInteger::$msb

staticprotected

Definition at line 170 of file BigInteger.php.

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

$precision

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

Precision.

See also

self::setPrecision() 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

phpseclib\Math\BigInteger::$value

Definition at line 192 of file BigInteger.php.

Referenced by phpseclib\Math\BigInteger\__construct(), phpseclib\Math\BigInteger\_trim(), phpseclib\Math\BigInteger\abs(), phpseclib\Math\BigInteger\bitwise_leftShift(), phpseclib\Math\BigInteger\bitwise_rightShift(), phpseclib\Math\BigInteger\copy(), phpseclib\Math\BigInteger\extendedGCD(), phpseclib\Math\BigInteger\isPrime(), and phpseclib\Math\BigInteger\toBytes().

BARRETT

const phpseclib\Math\BigInteger::BARRETT = 1

See also

BigInteger::_barrett()

Definition at line 79 of file BigInteger.php.

CLASSIC

const phpseclib\Math\BigInteger::CLASSIC = 3

See also

BigInteger::_remainder()

Definition at line 87 of file BigInteger.php.

DATA

const phpseclib\Math\BigInteger::DATA = 1

$cache[self::DATA] contains the cached data.

Definition at line 126 of file BigInteger.php.

KARATSUBA_CUTOFF

const phpseclib\Math\BigInteger::KARATSUBA_CUTOFF = 25

#-

Karatsuba Cutoff

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

private

Definition at line 160 of file BigInteger.php.

MODE_BCMATH

const phpseclib\Math\BigInteger::MODE_BCMATH = 2

To use the BCMath library.

(if enabled; otherwise, the internal implementation will be used)

Definition at line 144 of file BigInteger.php.

MODE_GMP

const phpseclib\Math\BigInteger::MODE_GMP = 3

To use the GMP library.

(if present; otherwise, either the BCMath or the internal implementation will be used)

Definition at line 150 of file BigInteger.php.

MODE_INTERNAL

const phpseclib\Math\BigInteger::MODE_INTERNAL = 1

#-

#+ Mode constants.

private

See also

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

Definition at line 138 of file BigInteger.php.

MONTGOMERY

const phpseclib\Math\BigInteger::MONTGOMERY = 0

#+ Reduction constants

private

See also

BigInteger::_reduce()

BigInteger::_montgomery()

BigInteger::_prepMontgomery()

Definition at line 75 of file BigInteger.php.

NONE

const phpseclib\Math\BigInteger::NONE = 4

See also

BigInteger::__clone()

Definition at line 91 of file BigInteger.php.

POWEROF2

const phpseclib\Math\BigInteger::POWEROF2 = 2

See also

BigInteger::_mod2()

Definition at line 83 of file BigInteger.php.

SIGN

const phpseclib\Math\BigInteger::SIGN = 1

$result[self::SIGN] contains the sign.

Definition at line 109 of file BigInteger.php.

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.

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

Definition at line 105 of file BigInteger.php.

VARIABLE

const phpseclib\Math\BigInteger::VARIABLE = 0

#-

#+ 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.

---

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

• libs/composer/vendor/phpseclib/phpseclib/phpseclib/Math/BigInteger.php