lib/3rdParty/phpseclib/Math/BigInteger.php

Properties

Description

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. PHP versions 4 and 5 {@internal (all DocBlock comments regarding implementation - such as the one that follows - refer to the {@link MATH_BIGINTEGER_MODE_INTERNAL MATH_BIGINTEGER_MODE_INTERNAL} mode) Math_BigInteger uses base-2**26 to perform operations such as multiplication and division and base-2**52 (ie. two base 2**26 digits) to perform addition and subtraction. Because the largest possible value when multiplying two base-2**26 numbers together is a base-2**52 number, double precision floating point numbers - numbers that should be supported on most hardware and whose significand is 53 bits - are used. As a consequence, bitwise operators such as >> and << cannot be used, nor can the modulo operator %, which only supports integers. Although this fact will slow this library down, the fact that such a high base is being used should more than compensate. When PHP version 6 is officially released, we'll be able to use 64-bit integers. This should, once again, allow bitwise operators, and will increase the maximum possible base to 2**31 (or 2**62 for addition / subtraction). Numbers are stored in {@link http://en.wikipedia.org/wiki/Endianness little endian} format. ie. (new Math_BigInteger(pow(2, 26)))->value = array(0, 1) Useful resources are as follows: - {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf Handbook of Applied Cryptography (HAC)} - {@link http://math.libtomcrypt.com/files/tommath.pdf Multi-Precision Math (MPM)} - Java's BigInteger classes. See /j2se/src/share/classes/java/math in jdk-1_5_0-src-jrl.zip Here's an example of how to use this library: add($b); echo $c->toString(); // outputs 5 ?> LICENSE: Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.

Constants

  MATH_BIGINTEGER_MONTGOMERY = 0




  MATH_BIGINTEGER_BARRETT = 1




  MATH_BIGINTEGER_POWEROF2 = 2




  MATH_BIGINTEGER_CLASSIC = 3




  MATH_BIGINTEGER_NONE = 4




  MATH_BIGINTEGER_VALUE = 0

$result[MATH_BIGINTEGER_VALUE] contains the value.


  MATH_BIGINTEGER_SIGN = 1

$result[MATH_BIGINTEGER_SIGN] contains the sign.


  MATH_BIGINTEGER_VARIABLE = 0

Cache constants
$cache[MATH_BIGINTEGER_VARIABLE] tells us whether or not the cached data is still valid.

  MATH_BIGINTEGER_DATA = 1

$cache[MATH_BIGINTEGER_DATA] contains the cached data.


  MATH_BIGINTEGER_MODE_INTERNAL = 1

To use the pure-PHP implementation


  MATH_BIGINTEGER_MODE_BCMATH = 2

To use the BCMath library
(if enabled; otherwise, the internal implementation will be used)

  MATH_BIGINTEGER_MODE_GMP = 3

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

  MATH_BIGINTEGER_MAX_DIGIT52 = pow(2, 52)

The largest digit that may be used in addition / subtraction
(we do pow(2, 52) instead of using 4503599627370496, directly, because some PHP installations will truncate 4503599627370496)

  MATH_BIGINTEGER_KARATSUBA_CUTOFF = 25

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

  MATH_BIGINTEGER_MODE = MATH_BIGINTEGER_MODE_INTERNAL




Classes

Math_BigInteger

Properties

 
 
public  
 
No 
No 

Description

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

Methods

Math_BigInteger, __clone, __sleep, __wakeup, _add, _array_repeat, _barrett, _base256_lshift, _base256_rshift, _baseSquare, _bytes2int, _compare, _divide_digit, _int2bytes, _karatsuba, _karatsubaSquare, _lshift, _make_odd, _mod2, _modInverse67108864, _montgomery, _montgomeryMultiply, _multiply, _multiplyLower, _multiplyReduce, _normalize, _prepMontgomery, _prepareReduce, _reduce, _regularBarrett, _regularMultiply, _rshift, _slidingWindow, _square, _squareReduce, _subtract, _trim, abs, bitwise_leftRotate, bitwise_rightRotate, copy, equals, extendedGCD, gcd, multiply, powMod, random, setPrecision, setRandomGenerator,

Math_BigInteger( \optional   $x = 0,   $base = 10, ) : \Math_BigInteger

Description

Converts base-2, base-10, base-16, and binary strings (eg. 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: toString(); // outputs 50 ?>

Arguments

Name Type Description Default
$x \optional

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

0
$base n/a 10

Return value

Type Description
\Math_BigInteger

Tags

Name Description
access public

__clone( ) : \Math_BigInteger

Description

__clone() magic method
Although you can call Math_BigInteger::__toString() directly in PHP5, you cannot call Math_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 Math_BigInteger::copy(), instead.

Return value

Type Description
\Math_BigInteger

Tags

Name Description
access public
see

__sleep( ) : n/a

Description

__sleep() magic method
Will be called, automatically, when serialize() is called on a Math_BigInteger object.

Return value

Type Description
n/a n/a

Tags

Name Description
see
access public

__wakeup( ) : n/a

Description

__wakeup() magic method
Will be called, automatically, when unserialize() is called on a Math_BigInteger object.

Return value

Type Description
n/a n/a

Tags

Name Description
see
access public

_add( Array   $x_value, Boolean   $x_negative, Array   $y_value, Boolean   $y_negative, ) : Array

Description

Performs addition.

Arguments

Name Type Description Default
$x_value Array
$x_negative Boolean
$y_value Array
$y_negative Boolean

Return value

Type Description
Array

Tags

Name Description
access private

_array_repeat(   $input,   $multiplier, ) : Array

Description

Array Repeat

Arguments

Name Type Description Default
$input n/a

Array

$multiplier n/a

mixed

Return value

Type Description
Array

Tags

Name Description
access private

_barrett( Array   $n, Array   $m, ) : Array

Description

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.

Arguments

Name Type Description Default
$n Array
$m Array

Return value

Type Description
Array

Tags

Name Description
see
access private

_base256_lshift(   $x,   $shift, ) : String

Description

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

Arguments

Name Type Description Default
$x n/a

String

$shift n/a

Integer

Return value

Type Description
String

Tags

Name Description
access private

_base256_rshift(   $x,   $shift, ) : String

Description

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

Arguments

Name Type Description Default
$x n/a

String

$shift n/a

Integer

Return value

Type Description
String

Tags

Name Description
access private

_baseSquare( Array   $value, ) : Array

Description

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.

Arguments

Name Type Description Default
$value Array

Return value

Type Description
Array

Tags

Name Description
access private

_bytes2int( String   $x, ) : Integer

Description

Converts bytes to 32-bit integers

Arguments

Name Type Description Default
$x String

Return value

Type Description
Integer

Tags

Name Description
access private

_compare( Array   $x_value, Boolean   $x_negative, Array   $y_value, Boolean   $y_negative, ) : Integer

Description

Compares two numbers.

Arguments

Name Type Description Default
$x_value Array
$x_negative Boolean
$y_value Array
$y_negative Boolean

Return value

Type Description
Integer

Tags

Name Description
see
access private

_divide_digit( Array   $dividend, Array   $divisor, ) : Array

Description

Divides a BigInteger by a regular integer
abc / x = a00 / x + b0 / x + c / x

Arguments

Name Type Description Default
$dividend Array
$divisor Array

Return value

Type Description
Array

Tags

Name Description
access private

_int2bytes( Integer   $x, ) : String

Description

Converts 32-bit integers to bytes.

Arguments

Name Type Description Default
$x Integer

Return value

Type Description
String

Tags

Name Description
access private

_karatsuba( Array   $x_value, Array   $y_value, ) : Array

Description

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

Arguments

Name Type Description Default
$x_value Array
$y_value Array

Return value

Type Description
Array

Tags

Name Description
access private

_karatsubaSquare( Array   $value, ) : Array

Description

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

Arguments

Name Type Description Default
$value Array

Return value

Type Description
Array

Tags

Name Description
access private

_lshift( Integer   $shift, ) : n/a

Description

Logical Left Shift
Shifts BigInteger's by $shift bits.

Arguments

Name Type Description Default
$shift Integer

Return value

Type Description
n/a n/a

Tags

Name Description
access private

_make_odd( ) : n/a

Description

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.

Return value

Type Description
n/a n/a

Tags

Name Description
see
access private

_mod2(   $n, ) : \Math_BigInteger

Description

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.

Arguments

Name Type Description Default
$n n/a

Return value

Type Description
\Math_BigInteger

Tags

Name Description
see
access private

_modInverse67108864( Array   $x, ) : Integer

Description

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!

Arguments

Name Type Description Default
$x Array

Return value

Type Description
Integer

Tags

Name Description
see
access private

_montgomery( Array   $x, Array   $n, ) : Array

Description

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.

Arguments

Name Type Description Default
$x Array
$n Array

Return value

Type Description
Array

Tags

Name Description
see
see
access private

_montgomeryMultiply( Array   $x, Array   $y, Array   $m, ) : Array

Description

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}

Arguments

Name Type Description Default
$x Array
$y Array
$m Array

Return value

Type Description
Array

Tags

Name Description
see
see
access private

_multiply( Array   $x_value, Boolean   $x_negative, Array   $y_value, Boolean   $y_negative, ) : Array

Description

Performs multiplication.

Arguments

Name Type Description Default
$x_value Array
$x_negative Boolean
$y_value Array
$y_negative Boolean

Return value

Type Description
Array

Tags

Name Description
access private

_multiplyLower( Array   $x_value, Boolean   $x_negative, Array   $y_value, Boolean   $y_negative,   $stop, ) : Array

Description

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.

Arguments

Name Type Description Default
$x_value Array
$x_negative Boolean
$y_value Array
$y_negative Boolean
$stop n/a

Return value

Type Description
Array

Tags

Name Description
see
access private

_multiplyReduce( Array   $x, Array   $y, Array   $n, Integer   $mode, ) : Array

Description

Modular multiply

Arguments

Name Type Description Default
$x Array
$y Array
$n Array
$mode Integer

Return value

Type Description
Array

Tags

Name Description
see
access private

_normalize(   $result, ) : \Math_BigInteger

Description

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

Arguments

Name Type Description Default
$result n/a

Return value

Type Description
\Math_BigInteger

Tags

Name Description
see
access private

_prepMontgomery( Array   $x, Array   $n, ) : Array

Description

Prepare a number for use in Montgomery Modular Reductions

Arguments

Name Type Description Default
$x Array
$n Array

Return value

Type Description
Array

Tags

Name Description
see
see
access private

_prepareReduce( Array   $x, Array   $n, Integer   $mode, ) : Array

Description

Modular reduction preperation

Arguments

Name Type Description Default
$x Array
$n Array
$mode Integer

Return value

Type Description
Array

Tags

Name Description
see
access private

_reduce( Array   $x, Array   $n, Integer   $mode, ) : Array

Description

Modular reduction
For most $modes this will return the remainder.

Arguments

Name Type Description Default
$x Array
$n Array
$mode Integer

Return value

Type Description
Array

Tags

Name Description
see
access private

_regularBarrett( Array   $x, Array   $n, ) : Array

Description

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

Arguments

Name Type Description Default
$x Array
$n Array

Return value

Type Description
Array

Tags

Name Description
see
access private

_regularMultiply( Array   $x_value, Array   $y_value, ) : Array

Description

Performs long multiplication on two BigIntegers
Modeled after 'multiply' in MutableBigInteger.java.

Arguments

Name Type Description Default
$x_value Array
$y_value Array

Return value

Type Description
Array

Tags

Name Description
access private

_rshift( Integer   $shift, ) : n/a

Description

Logical Right Shift
Shifts BigInteger's by $shift bits.

Arguments

Name Type Description Default
$shift Integer

Return value

Type Description
n/a n/a

Tags

Name Description
access private

_slidingWindow( \Math_BigInteger   $e, \Math_BigInteger   $n, Integer   $mode, ) : \Math_BigInteger

Description

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.

Arguments

Name Type Description Default
$e \Math_BigInteger
$n \Math_BigInteger
$mode Integer

Return value

Type Description
\Math_BigInteger

Tags

Name Description
access private

_square( Array   $x = false, ) : Array

Description

Performs squaring

Arguments

Name Type Description Default
$x Array false

Return value

Type Description
Array

Tags

Name Description
access private

_squareReduce( Array   $x, Array   $n, Integer   $mode, ) : Array

Description

Modular square

Arguments

Name Type Description Default
$x Array
$n Array
$mode Integer

Return value

Type Description
Array

Tags

Name Description
see
access private

_subtract( Array   $x_value, Boolean   $x_negative, Array   $y_value, Boolean   $y_negative, ) : Array

Description

Performs subtraction.

Arguments

Name Type Description Default
$x_value Array
$x_negative Boolean
$y_value Array
$y_negative Boolean

Return value

Type Description
Array

Tags

Name Description
access private

_trim(   $value, ) : \Math_BigInteger

Description

Trim
Removes leading zeros

Arguments

Name Type Description Default
$value n/a

Return value

Type Description
\Math_BigInteger

Tags

Name Description
access private

abs( ) : \Math_BigInteger

Description

Absolute value.

Return value

Type Description
\Math_BigInteger

Tags

Name Description
access public

bitwise_leftRotate( Integer   $shift, ) : \Math_BigInteger

Description

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

Arguments

Name Type Description Default
$shift Integer

Return value

Type Description
\Math_BigInteger

Tags

Name Description
access public

bitwise_rightRotate( Integer   $shift, ) : \Math_BigInteger

Description

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

Arguments

Name Type Description Default
$shift Integer

Return value

Type Description
\Math_BigInteger

Tags

Name Description
access public

copy( ) : \Math_BigInteger

Description

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 value

Type Description
\Math_BigInteger

Tags

Name Description
access public
see

equals( \Math_BigInteger   $x, ) : Boolean

Description

Tests the equality of two numbers.
If you need to see if one number is greater than or less than another number, use Math_BigInteger::compare()

Arguments

Name Type Description Default
$x \Math_BigInteger

Return value

Type Description
Boolean

Tags

Name Description
access public
see

extendedGCD(   $n, ) : n/a

Arguments

Name Type Description Default
$n n/a

Return value

Type Description
n/a n/a

gcd( \Math_BigInteger   $n, ) : \Math_BigInteger

Description

Calculates the greatest common divisor
Say you have 693 and 609. The GCD is 21. Here's an example: extendedGCD($b); echo $gcd->toString() . "\r\n"; // outputs 21 ?>

Arguments

Name Type Description Default
$n \Math_BigInteger

Return value

Type Description
\Math_BigInteger

Tags

Name Description
access public

multiply( \Math_BigInteger   $x, ) : \Math_BigInteger

Description

Multiplies two BigIntegers
Here's an example: multiply($b); echo $c->toString(); // outputs 200 ?>

Arguments

Name Type Description Default
$x \Math_BigInteger

Return value

Type Description
\Math_BigInteger

Tags

Name Description
access public

powMod( \Math_BigInteger   $e, \Math_BigInteger   $n, ) : \Math_BigInteger

Description

Performs modular exponentiation.
Alias for Math_BigInteger::modPow()

Arguments

Name Type Description Default
$e \Math_BigInteger
$n \Math_BigInteger

Return value

Type Description
\Math_BigInteger

Tags

Name Description
access public

random(   $min = false,   $max = false, ) : \Math_BigInteger

Description

Generate a random number

Arguments

Name Type Description Default
$min n/a false
$max n/a false

Return value

Type Description
\Math_BigInteger

Tags

Name Description
access public

setPrecision(   $bits, ) : \Math_BigInteger

Description

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

Arguments

Name Type Description Default
$bits n/a

Return value

Type Description
\Math_BigInteger

Tags

Name Description
access public

setRandomGenerator(   $generator, ) : n/a

Description

Set random number generator function
$generator should be the name of a random generating function whose first parameter is the minimum value and whose second parameter is the maximum value. If this function needs to be seeded, it should be seeded prior to calling Math_BigInteger::random() or Math_BigInteger::randomPrime() If the random generating function is not explicitly set, it'll be assumed to be mt_rand().

Arguments

Name Type Description Default
$generator n/a

Return value

Type Description
n/a n/a

Tags

Name Description
see
see
access public

Properties

$bitmask, $generator, $hex, $is_negative, $precision, $value,

  public  $bitmask = false

Precision Bitmask


  public  $generator = 'mt_rand'

Random number generator function


String  public  $hex =

Mode independant value used for serialization.
If the bcmath or gmp extensions are installed $this->value will be a non-serializable resource, hence the need for a variable that'll be serializable regardless of whether or not extensions are being used. Unlike $this->value, however, $this->hex is only calculated when $this->__sleep() is called.

Boolean  public  $is_negative = false

Holds the BigInteger's magnitude.


  public  $precision = -1

Precision


Array  public  $value =

Holds the BigInteger's value.


Documentation was generated by phpDocumentor 2.0.1 .

Namespaces

  • global

    Packages