[ Index ]

PHP Cross Reference of DokuWiki

title

Body

[close]

/vendor/phpseclib/phpseclib/phpseclib/Math/ -> BigInteger.php (summary)

Pure-PHP arbitrary precision integer arithmetic library. Supports base-2, base-10, base-16, and base-256 numbers.  Uses the GMP or BCMath extensions, if available, and an internal implementation, otherwise.

Author: Jim Wigginton
Copyright: 2006 Jim Wigginton
License: http://www.opensource.org/licenses/mit-license.html MIT License
File Size: 3787 lines (126 kb)
Included or required:0 times
Referenced: 0 times
Includes or requires: 0 files

Defines 1 class

BigInteger:: (71 methods):
  __construct()
  toBytes()
  toHex()
  toBits()
  toString()
  copy()
  __toString()
  __clone()
  __sleep()
  __wakeup()
  __debugInfo()
  add()
  _add()
  subtract()
  _subtract()
  multiply()
  _multiply()
  _regularMultiply()
  _karatsuba()
  _square()
  _baseSquare()
  _karatsubaSquare()
  divide()
  _divide_digit()
  modPow()
  powMod()
  _slidingWindow()
  _reduce()
  _prepareReduce()
  _multiplyReduce()
  _squareReduce()
  _mod2()
  _barrett()
  _regularBarrett()
  _multiplyLower()
  _montgomery()
  _montgomeryMultiply()
  _prepMontgomery()
  _modInverse67108864()
  modInverse()
  extendedGCD()
  gcd()
  abs()
  compare()
  _compare()
  equals()
  setPrecision()
  bitwise_and()
  bitwise_or()
  bitwise_xor()
  bitwise_not()
  bitwise_rightShift()
  bitwise_leftShift()
  bitwise_leftRotate()
  bitwise_rightRotate()
  _random_number_helper()
  random()
  randomPrime()
  _make_odd()
  isPrime()
  _lshift()
  _rshift()
  _normalize()
  _trim()
  _array_repeat()
  _base256_lshift()
  _base256_rshift()
  _int2bytes()
  _bytes2int()
  _encodeASN1Length()
  _safe_divide()


Class: BigInteger  - X-Ref

Pure-PHP arbitrary precision integer arithmetic library. Supports base-2, base-10, base-16, and base-256
numbers.

__construct($x = 0, $base = 10)   X-Ref
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:
<code>
<?php
$a = new \phpseclib\Math\BigInteger('0x32', 16); // 50 in base-16

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

param: $x base-10 number or base-$base number if $base set.
param: int $base
return: \phpseclib\Math\BigInteger

toBytes($twos_compliment = false)   X-Ref
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:
<code>
<?php
$a = new \phpseclib\Math\BigInteger('65');

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

param: bool $twos_compliment
return: string

toHex($twos_compliment = false)   X-Ref
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:
<code>
<?php
$a = new \phpseclib\Math\BigInteger('65');

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

param: bool $twos_compliment
return: string

toBits($twos_compliment = false)   X-Ref
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:
<code>
<?php
$a = new \phpseclib\Math\BigInteger('65');

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

param: bool $twos_compliment
return: string

toString()   X-Ref
Converts a BigInteger to a base-10 number.

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

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

return: string

copy()   X-Ref
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:

{@link http://php.net/language.oop5.basic#51624}

return: \phpseclib\Math\BigInteger
see: self::__clone()

__toString()   X-Ref
__toString() magic method

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


__clone()   X-Ref
__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.

return: \phpseclib\Math\BigInteger
see: self::copy()

__sleep()   X-Ref
__sleep() magic method

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

see: self::__wakeup()

__wakeup()   X-Ref
__wakeup() magic method

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

see: self::__sleep()

__debugInfo()   X-Ref
__debugInfo() magic method

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


add($y)   X-Ref
Adds two BigIntegers.

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

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

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

param: \phpseclib\Math\BigInteger $y
return: \phpseclib\Math\BigInteger

_add($x_value, $x_negative, $y_value, $y_negative)   X-Ref
Performs addition.

param: array $x_value
param: bool $x_negative
param: array $y_value
param: bool $y_negative
return: array

subtract($y)   X-Ref
Subtracts two BigIntegers.

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

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

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

param: \phpseclib\Math\BigInteger $y
return: \phpseclib\Math\BigInteger

_subtract($x_value, $x_negative, $y_value, $y_negative)   X-Ref
Performs subtraction.

param: array $x_value
param: bool $x_negative
param: array $y_value
param: bool $y_negative
return: array

multiply($x)   X-Ref
Multiplies two BigIntegers

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

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

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

param: \phpseclib\Math\BigInteger $x
return: \phpseclib\Math\BigInteger

_multiply($x_value, $x_negative, $y_value, $y_negative)   X-Ref
Performs multiplication.

param: array $x_value
param: bool $x_negative
param: array $y_value
param: bool $y_negative
return: array

_regularMultiply($x_value, $y_value)   X-Ref
Performs long multiplication on two BigIntegers

Modeled after 'multiply' in MutableBigInteger.java.

param: array $x_value
param: array $y_value
return: array

_karatsuba($x_value, $y_value)   X-Ref
Performs Karatsuba multiplication on two BigIntegers

See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and
{@link http://math.libtomcrypt.com/files/tommath.pdf#page=120 MPM 5.2.3}.

param: array $x_value
param: array $y_value
return: array

_square($x = false)   X-Ref
Performs squaring

param: array $x
return: array

_baseSquare($value)   X-Ref
Performs traditional squaring on two BigIntegers

Squaring can be done faster than multiplying a number by itself can be.  See
{@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=7 HAC 14.2.4} /
{@link http://math.libtomcrypt.com/files/tommath.pdf#page=141 MPM 5.3} for more information.

param: array $value
return: array

_karatsubaSquare($value)   X-Ref
Performs Karatsuba "squaring" on two BigIntegers

See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and
{@link http://math.libtomcrypt.com/files/tommath.pdf#page=151 MPM 5.3.4}.

param: array $value
return: array

divide($y)   X-Ref
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:
<code>
<?php
$a = new \phpseclib\Math\BigInteger('10');
$b = new \phpseclib\Math\BigInteger('20');

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

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

param: \phpseclib\Math\BigInteger $y
return: array

_divide_digit($dividend, $divisor)   X-Ref
Divides a BigInteger by a regular integer

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

param: array $dividend
param: array $divisor
return: array

modPow($e, $n)   X-Ref
Performs modular exponentiation.

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

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

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

param: \phpseclib\Math\BigInteger $e
param: \phpseclib\Math\BigInteger $n
return: \phpseclib\Math\BigInteger

powMod($e, $n)   X-Ref
Performs modular exponentiation.

Alias for modPow().

param: \phpseclib\Math\BigInteger $e
param: \phpseclib\Math\BigInteger $n
return: \phpseclib\Math\BigInteger

_slidingWindow($e, $n, $mode)   X-Ref
Sliding Window k-ary Modular Exponentiation

Based on {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=27 HAC 14.85} /
{@link http://math.libtomcrypt.com/files/tommath.pdf#page=210 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.

param: \phpseclib\Math\BigInteger $e
param: \phpseclib\Math\BigInteger $n
param: int $mode
return: \phpseclib\Math\BigInteger

_reduce($x, $n, $mode)   X-Ref
Modular reduction

For most $modes this will return the remainder.

param: array $x
param: array $n
param: int $mode
return: array
see: self::_slidingWindow()

_prepareReduce($x, $n, $mode)   X-Ref
Modular reduction preperation

param: array $x
param: array $n
param: int $mode
return: array
see: self::_slidingWindow()

_multiplyReduce($x, $y, $n, $mode)   X-Ref
Modular multiply

param: array $x
param: array $y
param: array $n
param: int $mode
return: array
see: self::_slidingWindow()

_squareReduce($x, $n, $mode)   X-Ref
Modular square

param: array $x
param: array $n
param: int $mode
return: array
see: self::_slidingWindow()

_mod2($n)   X-Ref
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.

param: \phpseclib\Math\BigInteger
return: \phpseclib\Math\BigInteger
see: self::_slidingWindow()

_barrett($n, $m)   X-Ref
Barrett Modular Reduction

See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=14 HAC 14.3.3} /
{@link http://math.libtomcrypt.com/files/tommath.pdf#page=165 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
{@link http://www.cosic.esat.kuleuven.be/publications/thesis-149.pdf#page=66 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
{@link http://math.libtomcrypt.com/files/tommath.pdf#page=162 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.

param: array $n
param: array $m
return: array
see: self::_slidingWindow()

_regularBarrett($x, $n)   X-Ref
(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.

param: array $x
param: array $n
return: array
see: self::_slidingWindow()

_multiplyLower($x_value, $x_negative, $y_value, $y_negative, $stop)   X-Ref
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.

param: array $x_value
param: bool $x_negative
param: array $y_value
param: bool $y_negative
param: int $stop
return: array
see: self::_regularBarrett()

_montgomery($x, $n)   X-Ref
Montgomery Modular Reduction

($x->_prepMontgomery($n))->_montgomery($n) yields $x % $n.
{@link http://math.libtomcrypt.com/files/tommath.pdf#page=170 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.

param: array $x
param: array $n
return: array
see: self::_prepMontgomery()
see: self::_slidingWindow()

_montgomeryMultiply($x, $y, $m)   X-Ref
Montgomery Multiply

Interleaves the montgomery reduction and long multiplication algorithms together as described in
{@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=13 HAC 14.36}

param: array $x
param: array $y
param: array $m
return: array
see: self::_prepMontgomery()
see: self::_montgomery()

_prepMontgomery($x, $n)   X-Ref
Prepare a number for use in Montgomery Modular Reductions

param: array $x
param: array $n
return: array
see: self::_montgomery()
see: self::_slidingWindow()

_modInverse67108864($x)   X-Ref
Modular Inverse of a number mod 2**26 (eg. 67108864)

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

{@link http://www-cs-students.stanford.edu/~tjw/jsbn/jsbn.js}

The following URL provides more info:

{@link 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!

param: array $x
return: int
see: self::_montgomery()

modInverse($n)   X-Ref
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:
<code>
<?php
$a = new \phpseclib\Math\BigInteger(30);
$b = new \phpseclib\Math\BigInteger(17);

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

echo "\r\n";

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

param: \phpseclib\Math\BigInteger $n
return: \phpseclib\Math\BigInteger|false

extendedGCD($n)   X-Ref
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 dependent upon which mode is in use.  See
{@link http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity Bezout's identity - Wikipedia} for more information.

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

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

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

param: \phpseclib\Math\BigInteger $n
return: \phpseclib\Math\BigInteger

gcd($n)   X-Ref
Calculates the greatest common divisor

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

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

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

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

param: \phpseclib\Math\BigInteger $n
return: \phpseclib\Math\BigInteger

abs()   X-Ref
Absolute value.

return: \phpseclib\Math\BigInteger

compare($y)   X-Ref
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).

param: \phpseclib\Math\BigInteger $y
return: int < 0 if $this is less than $y; > 0 if $this is greater than $y, and 0 if they are equal.
see: self::equals()

_compare($x_value, $x_negative, $y_value, $y_negative)   X-Ref
Compares two numbers.

param: array $x_value
param: bool $x_negative
param: array $y_value
param: bool $y_negative
return: int
see: self::compare()

equals($x)   X-Ref
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()

param: \phpseclib\Math\BigInteger $x
return: bool
see: self::compare()

setPrecision($bits)   X-Ref
Set Precision

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

param: int $bits

bitwise_and($x)   X-Ref
Logical And

param: \phpseclib\Math\BigInteger $x
return: \phpseclib\Math\BigInteger

bitwise_or($x)   X-Ref
Logical Or

param: \phpseclib\Math\BigInteger $x
return: \phpseclib\Math\BigInteger

bitwise_xor($x)   X-Ref
Logical Exclusive-Or

param: \phpseclib\Math\BigInteger $x
return: \phpseclib\Math\BigInteger

bitwise_not()   X-Ref
Logical Not

return: \phpseclib\Math\BigInteger

bitwise_rightShift($shift)   X-Ref
Logical Right Shift

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

param: int $shift
return: \phpseclib\Math\BigInteger

bitwise_leftShift($shift)   X-Ref
Logical Left Shift

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

param: int $shift
return: \phpseclib\Math\BigInteger

bitwise_leftRotate($shift)   X-Ref
Logical Left Rotate

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

param: int $shift
return: \phpseclib\Math\BigInteger

bitwise_rightRotate($shift)   X-Ref
Logical Right Rotate

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

param: int $shift
return: \phpseclib\Math\BigInteger

_random_number_helper($size)   X-Ref
Generates a random BigInteger

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

param: int $length
return: \phpseclib\Math\BigInteger

random($arg1, $arg2 = false)   X-Ref
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)

param: \phpseclib\Math\BigInteger $arg1
param: \phpseclib\Math\BigInteger $arg2
return: \phpseclib\Math\BigInteger

randomPrime($arg1, $arg2 = false, $timeout = false)   X-Ref
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.

param: \phpseclib\Math\BigInteger $arg1
param: \phpseclib\Math\BigInteger $arg2
param: int $timeout
return: Math_BigInteger|false

_make_odd()   X-Ref
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: self::randomPrime()

isPrime($t = false)   X-Ref
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.

param: \phpseclib\Math\BigInteger $t
return: bool

_lshift($shift)   X-Ref
Logical Left Shift

Shifts BigInteger's by $shift bits.

param: int $shift

_rshift($shift)   X-Ref
Logical Right Shift

Shifts BigInteger's by $shift bits.

param: int $shift

_normalize($result)   X-Ref
Normalize

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

param: \phpseclib\Math\BigInteger
return: \phpseclib\Math\BigInteger
see: self::_trim()

_trim($value)   X-Ref
Trim

Removes leading zeros

param: array $value
return: \phpseclib\Math\BigInteger

_array_repeat($input, $multiplier)   X-Ref
Array Repeat

param: $input Array
param: $multiplier mixed
return: array

_base256_lshift(&$x, $shift)   X-Ref
Logical Left Shift

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

param: $x String
param: $shift Integer
return: string

_base256_rshift(&$x, $shift)   X-Ref
Logical Right Shift

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

param: $x String
param: $shift Integer
return: string

_int2bytes($x)   X-Ref
Converts 32-bit integers to bytes.

param: int $x
return: string

_bytes2int($x)   X-Ref
Converts bytes to 32-bit integers

param: string $x
return: int

_encodeASN1Length($length)   X-Ref
DER-encode an integer

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

param: int $length
return: string
see: self::modPow()

_safe_divide($x, $y)   X-Ref
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.

param: int $x
param: int $y
return: int