[ Index ] |
PHP Cross Reference of DokuWiki |
[Source view] [Print] [Project Stats]
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 |
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__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: int|string|resource $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 $n 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 that is < 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 $size 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 $result 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: array $input param: mixed $multiplier return: array |
_base256_lshift(&$x, $shift) X-Ref |
Logical Left Shift Shifts binary strings $shift bits, essentially multiplying by 2**$shift. param: string $x (by reference) param: int $shift 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: string $x (by referenc) param: int $shift 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 |