Pure-PHP arbitrary precision integer arithmetic library.

Supports base-2, base-10, base-16, and base-256 numbers.

author | Jim Wigginton
version | 1.0.0RC4
access | public
package | Math_BigInteger

### Methods

## Converts base-2, base-10, base-16, and binary strings (eg.

    Math_BigInteger(\optional $x, \optional $base) : \Math_BigInteger

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
    ?>

access | public

### Parameters

#### $x

`\optional`

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

#### $base

`\optional`

integer $base

### Returns

`\Math_BigInteger`

## __clone() magic method

    __clone() : \Math_BigInteger

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.

access | public
see | \global\copy()

### Returns

`\Math_BigInteger`

## __sleep() magic method

    __sleep()

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

see | \global\__wakeup()
access | public

## __wakeup() magic method

    __wakeup()

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

see | \global\__sleep()
access | public

## Performs addition.

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

access | private

### Parameters

#### $x_value

`Array`

#### $x_negative

`Boolean`

#### $y_value

`Array`

#### $y_negative

`Boolean`

### Returns

`Array`

## Array Repeat

    _array_repeat(\$input $input, \$multiplier $multiplier) : Array

access | private

### Parameters

#### $input

`\$input`

Array

#### $multiplier

`\$multiplier`

mixed

### Returns

`Array`

## Barrett Modular Reduction

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

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 | \global\_slidingWindow()
access | private

### Parameters

#### $n

`Array`

#### $m

`Array`

### Returns

`Array`

## Logical Left Shift

    _base256_lshift(\$x $x, \$shift $shift) : String

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

access | private

### Parameters

#### $x

`\$x`

String

#### $shift

`\$shift`

Integer

### Returns

`String`

## Logical Right Shift

    _base256_rshift(\$x $x, \$shift $shift) : String

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

access | private

### Parameters

#### $x

`\$x`

String

#### $shift

`\$shift`

Integer

### Returns

`String`

## Performs traditional squaring on two BigIntegers

    _baseSquare(Array $value) : Array

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

access | private

### Parameters

#### $value

`Array`

### Returns

`Array`

## Converts bytes to 32-bit integers

    _bytes2int(String $x) : Integer

access | private

### Parameters

#### $x

`String`

### Returns

`Integer`

## Compares two numbers.

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

see | \global\compare()
access | private

### Parameters

#### $x_value

`Array`

#### $x_negative

`Boolean`

#### $y_value

`Array`

#### $y_negative

`Boolean`

### Returns

`Integer`

## Divides a BigInteger by a regular integer

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

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

access | private

### Parameters

#### $dividend

`Array`

#### $divisor

`Array`

### Returns

`Array`

## Converts 32-bit integers to bytes.

    _int2bytes(Integer $x) : String

access | private

### Parameters

#### $x

`Integer`

### Returns

`String`

## Performs Karatsuba multiplication on two BigIntegers

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

See Karatsuba algorithm and MPM 5.2.3.

access | private

### Parameters

#### $x_value

`Array`

#### $y_value

`Array`

### Returns

`Array`

## Performs Karatsuba "squaring" on two BigIntegers

    _karatsubaSquare(Array $value) : Array

See Karatsuba algorithm and MPM 5.3.4.

access | private

### Parameters

#### $value

`Array`

### Returns

`Array`

## Logical Left Shift

    _lshift(Integer $shift)

Shifts BigInteger's by $shift bits.

access | private

### Parameters

#### $shift

`Integer`

## Make the current number odd

    _make_odd()

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

see | \global\randomPrime()
access | private

## Modulos for Powers of Two

    _mod2($n) : \Math_BigInteger

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 | \global\_slidingWindow()
access | private

### Parameters

#### $n

Math_BigInteger

### Returns

`\Math_BigInteger`

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

    _modInverse67108864(Array $x) : Integer

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 | \global\_montgomery()
access | private

### Parameters

#### $x

`Array`

### Returns

`Integer`

## Montgomery Modular Reduction

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

($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 | \global\_prepMontgomery()
see | \global\_slidingWindow()
access | private

### Parameters

#### $x

`Array`

#### $n

`Array`

### Returns

`Array`

## Montgomery Multiply

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

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

see | \global\_prepMontgomery()
see | \global\_montgomery()
access | private

### Parameters

#### $x

`Array`

#### $y

`Array`

#### $m

`Array`

### Returns

`Array`

## Performs multiplication.

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

access | private

### Parameters

#### $x_value

`Array`

#### $x_negative

`Boolean`

#### $y_value

`Array`

#### $y_negative

`Boolean`

### Returns

`Array`

## Performs long multiplication up to $stop digits

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

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

see | \global\_regularBarrett()
access | private

### Parameters

#### $x_value

`Array`

#### $x_negative

`Boolean`

#### $y_value

`Array`

#### $y_negative

`Boolean`

#### $stop

### Returns

`Array`

## Modular multiply

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

see | \global\_slidingWindow()
access | private

### Parameters

#### $x

`Array`

#### $y

`Array`

#### $n

`Array`

#### $mode

`Integer`

### Returns

`Array`

## Normalize

    _normalize($result) : \Math_BigInteger

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

see | \global\_trim()
access | private

### Parameters

#### $result

Math_BigInteger

### Returns

`\Math_BigInteger`

## Prepare a number for use in Montgomery Modular Reductions

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

see | \global\_montgomery()
see | \global\_slidingWindow()
access | private

### Parameters

#### $x

`Array`

#### $n

`Array`

### Returns

`Array`

## Modular reduction preperation

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

see | \global\_slidingWindow()
access | private

### Parameters

#### $x

`Array`

#### $n

`Array`

#### $mode

`Integer`

### Returns

`Array`

## Modular reduction

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

For most $modes this will return the remainder.

see | \global\_slidingWindow()
access | private

### Parameters

#### $x

`Array`

#### $n

`Array`

#### $mode

`Integer`

### Returns

`Array`

## (Regular) Barrett Modular Reduction

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

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.

see | \global\_slidingWindow()
access | private

### Parameters

#### $x

`Array`

#### $n

`Array`

### Returns

`Array`

## Performs long multiplication on two BigIntegers

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

Modeled after 'multiply' in MutableBigInteger.java.

access | private

### Parameters

#### $x_value

`Array`

#### $y_value

`Array`

### Returns

`Array`

## Logical Right Shift

    _rshift(Integer $shift)

Shifts BigInteger's by $shift bits.

access | private

### Parameters

#### $shift

`Integer`

## Sliding Window k-ary Modular Exponentiation

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

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.

access | private

### Parameters

#### $e

`\Math_BigInteger`

#### $n

`\Math_BigInteger`

#### $mode

`Integer`

### Returns

`\Math_BigInteger`

## Performs squaring

    _square(Array $x) : Array

access | private

### Parameters

#### $x

`Array`

### Returns

`Array`

## Modular square

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

see | \global\_slidingWindow()
access | private

### Parameters

#### $x

`Array`

#### $n

`Array`

#### $mode

`Integer`

### Returns

`Array`

## Performs subtraction.

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

access | private

### Parameters

#### $x_value

`Array`

#### $x_negative

`Boolean`

#### $y_value

`Array`

#### $y_negative

`Boolean`

### Returns

`Array`

## Trim

    _trim($value) : \Math_BigInteger

Removes leading zeros

access | private

### Parameters

#### $value

### Returns

`\Math_BigInteger`

## Absolute value.

    abs() : \Math_BigInteger

access | public

### Returns

`\Math_BigInteger`

## Logical Left Rotate

    bitwise_leftRotate(Integer $shift) : \Math_BigInteger

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

access | public

### Parameters

#### $shift

`Integer`

### Returns

`\Math_BigInteger`

## Logical Right Rotate

    bitwise_rightRotate(Integer $shift) : \Math_BigInteger

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

access | public

### Parameters

#### $shift

`Integer`

### Returns

`\Math_BigInteger`

## Copy an object

    copy() : \Math_BigInteger

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

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

access | public
see | \global\__clone()

### Returns

`\Math_BigInteger`

## Tests the equality of two numbers.

    equals(\Math_BigInteger $x) : Boolean

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

access | public
see | \global\compare()

### Parameters

#### $x

`\Math_BigInteger`

### Returns

`Boolean`

## extendedGCD()

    extendedGCD($n)

### Parameters

#### $n

## Calculates the greatest common divisor

    gcd(\Math_BigInteger $n) : \Math_BigInteger

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

Here's an example:

    extendedGCD($b);

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

access | public

### Parameters

#### $n

`\Math_BigInteger`

### Returns

`\Math_BigInteger`

## Multiplies two BigIntegers

    multiply(\Math_BigInteger $x) : \Math_BigInteger

Here's an example:

    multiply($b);

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

access | public

### Parameters

#### $x

`\Math_BigInteger`

### Returns

`\Math_BigInteger`

## Performs modular exponentiation.

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

Alias for Math_BigInteger::modPow()

access | public

### Parameters

#### $e

`\Math_BigInteger`

#### $n

`\Math_BigInteger`

### Returns

`\Math_BigInteger`

## Generate a random number

    random(\optional $min, \optional $max) : \Math_BigInteger

access | public

### Parameters

#### $min

`\optional`

Integer $min

#### $max

`\optional`

Integer $max

### Returns

`\Math_BigInteger`

## Set Precision

    setPrecision($bits) : \Math_BigInteger

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

access | public

### Parameters

#### $bits

### Returns

`\Math_BigInteger`

## Set random number generator function

    setRandomGenerator(\optional $generator)

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

see | \global\random()
see | \global\randomPrime()
access | public

### Parameters

#### $generator

`\optional`

String $generator

### Properties

## Precision Bitmask

    $bitmask

see | \global\setPrecision()
access | private

## Random number generator function

    $generator

see | \global\setRandomGenerator()
access | private

## Mode independant value used for serialization.

    $hex : String

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.

see | \global\__sleep()
see | \global\__wakeup()
access | private

## Holds the BigInteger's magnitude.

    $is_negative : Boolean

access | private

## Precision

    $precision

see | \global\setPrecision()
access | private

## Holds the BigInteger's value.

    $value : Array

access | private