Documentation

BigInteger
in package

BigInteger

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

BARRETT


    public
    mixed
    BARRETT
    = 1

CLASSIC


    public
    mixed
    CLASSIC
    = 3

DATA

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


    public
    mixed
    DATA
    = 1

KARATSUBA_CUTOFF

Karatsuba Cutoff


    public
    mixed
    KARATSUBA_CUTOFF
    = 25

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

MODE_BCMATH

To use the BCMath library


    public
    mixed
    MODE_BCMATH
    = 2

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

MODE_GMP

To use the GMP library


    public
    mixed
    MODE_GMP
    = 3

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

MODE_INTERNAL

To use the pure-PHP implementation


    public
    mixed
    MODE_INTERNAL
    = 1

MONTGOMERY


    public
    mixed
    MONTGOMERY
    = 0

NONE


    public
    mixed
    NONE
    = 4

POWEROF2


    public
    mixed
    POWEROF2
    = 2

SIGN

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


    public
    mixed
    SIGN
    = 1

VALUE

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


    public
    mixed
    VALUE
    = 0

VARIABLE

Cache constants


    public
    mixed
    VARIABLE
    = 0

$cache[self::VARIABLE] tells us whether or not the cached data is still valid.

$bitmask

Precision Bitmask


    public
        mixed
    $bitmask
     = false

$hex

Mode independent value used for serialization.


    public
        string
    $hex

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.

$is_negative

Holds the BigInteger's magnitude.


    public
        bool
    $is_negative
     = false

$precision

Precision


    public
        mixed
    $precision
     = -1

$value

Holds the BigInteger's value.


    public
        array<string|int, mixed>
    $value

$base


    protected
    static    mixed
    $base

$baseFull


    protected
    static    mixed
    $baseFull

$max10

$max10 in greatest $max10Len satisfying $max10 = 10**$max10Len <= 2**$base.


    protected
    static    mixed
    $max10

$max10Len

$max10Len in greatest $max10Len satisfying $max10 = 10**$max10Len <= 2**$base.


    protected
    static    mixed
    $max10Len

$maxDigit


    protected
    static    mixed
    $maxDigit

$maxDigit2


    protected
    static    mixed
    $maxDigit2

$msb


    protected
    static    mixed
    $msb

__clone()

__clone() magic method


    public
                __clone() : BigInteger

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 values

BigInteger —

__construct()

Converts base-2, base-10, base-16, and binary strings (base-256) to BigIntegers.


    public
                __construct( $x[, int $base = 10 ]) : BigInteger

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

Parameters

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

Return values

BigInteger —

__debugInfo()

__debugInfo() magic method


    public
                __debugInfo() : mixed

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

Return values

mixed —

__sleep()

__sleep() magic method


    public
                __sleep() : mixed

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

Return values

mixed —

__wakeup()

__wakeup() magic method


    public
                __wakeup() : mixed

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

Return values

mixed —

_add()

Performs addition.


    public
                _add(array<string|int, mixed> $x_value, bool $x_negative, array<string|int, mixed> $y_value, bool $y_negative) : array<string|int, mixed>

Parameters

$x_value : array<string|int, mixed>
$x_negative : bool
$y_value : array<string|int, mixed>
$y_negative : bool

Return values

array<string|int, mixed> —

_array_repeat()

Array Repeat


    public
                _array_repeat( $input,  $multiplier) : array<string|int, mixed>

Parameters

$input :: Array
$multiplier :: mixed

Return values

array<string|int, mixed> —

_barrett()

Barrett Modular Reduction


    public
                _barrett(array<string|int, mixed> $n, array<string|int, mixed> $m) : array<string|int, mixed>

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.

Parameters

$n : array<string|int, mixed>
$m : array<string|int, mixed>

Return values

array<string|int, mixed> —

_base256_lshift()

Logical Left Shift


    public
                _base256_lshift( &$x,  $shift) : string

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

Parameters

$x :: String
$shift :: Integer

Return values

string —

_base256_rshift()

Logical Right Shift


    public
                _base256_rshift( &$x,  $shift) : string

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

Parameters

$x :: String
$shift :: Integer

Return values

string —

_baseSquare()

Performs traditional squaring on two BigIntegers


    public
                _baseSquare(array<string|int, mixed> $value) : array<string|int, mixed>

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

$value : array<string|int, mixed>

Return values

array<string|int, mixed> —

_bytes2int()

Converts bytes to 32-bit integers


    public
                _bytes2int(string $x) : int

Parameters

$x : string

Return values

int —

_compare()

Compares two numbers.


    public
                _compare(array<string|int, mixed> $x_value, bool $x_negative, array<string|int, mixed> $y_value, bool $y_negative) : int

Parameters

$x_value : array<string|int, mixed>
$x_negative : bool
$y_value : array<string|int, mixed>
$y_negative : bool

Return values

int —

_divide_digit()

Divides a BigInteger by a regular integer


    public
                _divide_digit(array<string|int, mixed> $dividend, array<string|int, mixed> $divisor) : array<string|int, mixed>

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

Parameters

$dividend : array<string|int, mixed>
$divisor : array<string|int, mixed>

Return values

array<string|int, mixed> —

_encodeASN1Length()

DER-encode an integer


    public
                _encodeASN1Length(int $length) : string

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

Parameters

$length : int

Return values

string —

_int2bytes()

Converts 32-bit integers to bytes.


    public
                _int2bytes(int $x) : string

Parameters

$x : int

Return values

string —

_karatsuba()

Performs Karatsuba multiplication on two BigIntegers


    public
                _karatsuba(array<string|int, mixed> $x_value, array<string|int, mixed> $y_value) : array<string|int, mixed>

See Karatsuba algorithm and MPM 5.2.3.

Parameters

$x_value : array<string|int, mixed>
$y_value : array<string|int, mixed>

Return values

array<string|int, mixed> —

_karatsubaSquare()

Performs Karatsuba "squaring" on two BigIntegers


    public
                _karatsubaSquare(array<string|int, mixed> $value) : array<string|int, mixed>

See Karatsuba algorithm and MPM 5.3.4.

Parameters

$value : array<string|int, mixed>

Return values

array<string|int, mixed> —

_lshift()

Logical Left Shift


    public
                _lshift(int $shift) : mixed

Shifts BigInteger's by $shift bits.

Parameters

$shift : int

Return values

mixed —

_make_odd()

Make the current number odd


    public
                _make_odd() : mixed

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

Return values

mixed —

_mod2()

Modulos for Powers of Two


    public
                _mod2(mixed $n) : 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.

Parameters

$n : mixed

Return values

BigInteger —

_modInverse67108864()

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


    public
                _modInverse67108864(array<string|int, mixed> $x) : int

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

The following URL provides more info:

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!

Parameters

$x : array<string|int, mixed>

Return values

int —

_montgomery()

Montgomery Modular Reduction


    public
                _montgomery(array<string|int, mixed> $x, array<string|int, mixed> $n) : array<string|int, mixed>

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

Parameters

$x : array<string|int, mixed>
$n : array<string|int, mixed>

Return values

array<string|int, mixed> —

_montgomeryMultiply()

Montgomery Multiply


    public
                _montgomeryMultiply(array<string|int, mixed> $x, array<string|int, mixed> $y, array<string|int, mixed> $m) : array<string|int, mixed>

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

Parameters

$x : array<string|int, mixed>
$y : array<string|int, mixed>
$m : array<string|int, mixed>

Return values

array<string|int, mixed> —

_multiply()

Performs multiplication.


    public
                _multiply(array<string|int, mixed> $x_value, bool $x_negative, array<string|int, mixed> $y_value, bool $y_negative) : array<string|int, mixed>

Parameters

$x_value : array<string|int, mixed>
$x_negative : bool
$y_value : array<string|int, mixed>
$y_negative : bool

Return values

array<string|int, mixed> —

_multiplyLower()

Performs long multiplication up to $stop digits


    public
                _multiplyLower(array<string|int, mixed> $x_value, bool $x_negative, array<string|int, mixed> $y_value, bool $y_negative, int $stop) : array<string|int, mixed>

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

Parameters

$x_value : array<string|int, mixed>
$x_negative : bool
$y_value : array<string|int, mixed>
$y_negative : bool
$stop : int

Return values

array<string|int, mixed> —

_multiplyReduce()

Modular multiply


    public
                _multiplyReduce(array<string|int, mixed> $x, array<string|int, mixed> $y, array<string|int, mixed> $n, int $mode) : array<string|int, mixed>

Parameters

$x : array<string|int, mixed>
$y : array<string|int, mixed>
$n : array<string|int, mixed>
$mode : int

Return values

array<string|int, mixed> —

_normalize()

Normalize


    public
                _normalize(mixed $result) : BigInteger

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

Parameters

$result : mixed

Return values

BigInteger —

_prepareReduce()

Modular reduction preperation


    public
                _prepareReduce(array<string|int, mixed> $x, array<string|int, mixed> $n, int $mode) : array<string|int, mixed>

Parameters

$x : array<string|int, mixed>
$n : array<string|int, mixed>
$mode : int

Return values

array<string|int, mixed> —

_prepMontgomery()

Prepare a number for use in Montgomery Modular Reductions


    public
                _prepMontgomery(array<string|int, mixed> $x, array<string|int, mixed> $n) : array<string|int, mixed>

Parameters

$x : array<string|int, mixed>
$n : array<string|int, mixed>

Return values

array<string|int, mixed> —

_random_number_helper()

Generates a random BigInteger


    public
                _random_number_helper(mixed $size) : BigInteger

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

Parameters

$size : mixed

Return values

BigInteger —

_reduce()

Modular reduction


    public
                _reduce(array<string|int, mixed> $x, array<string|int, mixed> $n, int $mode) : array<string|int, mixed>

For most $modes this will return the remainder.

Parameters

$x : array<string|int, mixed>
$n : array<string|int, mixed>
$mode : int

Return values

array<string|int, mixed> —

_regularBarrett()

(Regular) Barrett Modular Reduction


    public
                _regularBarrett(array<string|int, mixed> $x, array<string|int, mixed> $n) : array<string|int, mixed>

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.

Parameters

$x : array<string|int, mixed>
$n : array<string|int, mixed>

Return values

array<string|int, mixed> —

_regularMultiply()

Performs long multiplication on two BigIntegers


    public
                _regularMultiply(array<string|int, mixed> $x_value, array<string|int, mixed> $y_value) : array<string|int, mixed>

Modeled after 'multiply' in MutableBigInteger.java.

Parameters

$x_value : array<string|int, mixed>
$y_value : array<string|int, mixed>

Return values

array<string|int, mixed> —

_rshift()

Logical Right Shift


    public
                _rshift(int $shift) : mixed

Shifts BigInteger's by $shift bits.

Parameters

$shift : int

Return values

mixed —

_safe_divide()

Single digit division


    public
                _safe_divide(int $x, int $y) : int

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.

Parameters

$x : int
$y : int

Return values

int —

_slidingWindow()

Sliding Window k-ary Modular Exponentiation


    public
                _slidingWindow(BigInteger $e, BigInteger $n, int $mode) : 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.

Parameters

$e : BigInteger
$n : BigInteger
$mode : int

Return values

BigInteger —

_square()

Performs squaring


    public
                _square([array<string|int, mixed> $x = false ]) : array<string|int, mixed>

Parameters

$x : array<string|int, mixed> = false

Return values

array<string|int, mixed> —

_squareReduce()

Modular square


    public
                _squareReduce(array<string|int, mixed> $x, array<string|int, mixed> $n, int $mode) : array<string|int, mixed>

Parameters

$x : array<string|int, mixed>
$n : array<string|int, mixed>
$mode : int

Return values

array<string|int, mixed> —

_subtract()

Performs subtraction.


    public
                _subtract(array<string|int, mixed> $x_value, bool $x_negative, array<string|int, mixed> $y_value, bool $y_negative) : array<string|int, mixed>

Parameters

$x_value : array<string|int, mixed>
$x_negative : bool
$y_value : array<string|int, mixed>
$y_negative : bool

Return values

array<string|int, mixed> —

_trim()

Trim


    public
                _trim(array<string|int, mixed> $value) : BigInteger

Removes leading zeros

Parameters

$value : array<string|int, mixed>

Return values

BigInteger —

abs()

Absolute value.


    public
                abs() : BigInteger

Return values

BigInteger —

bitwise_leftRotate()

Logical Left Rotate


    public
                bitwise_leftRotate(int $shift) : BigInteger

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

Parameters

$shift : int

Return values

BigInteger —

bitwise_rightRotate()

Logical Right Rotate


    public
                bitwise_rightRotate(int $shift) : BigInteger

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

Parameters

$shift : int

Return values

BigInteger —

copy()

Copy an object


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

Return values

BigInteger —

equals()

Tests the equality of two numbers.


    public
                equals(BigInteger $x) : bool

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

Parameters

$x : BigInteger

Return values

bool —

gcd()

Calculates the greatest common divisor


    public
                gcd(BigInteger $n) : BigInteger

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

Here's an example:


extendedGCD($b);

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

Parameters

$n : BigInteger

Return values

BigInteger —

multiply()

Multiplies two BigIntegers


    public
                multiply(BigInteger $x) : BigInteger

Here's an example:


multiply($b);

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

Parameters

$x : BigInteger

Return values

BigInteger —

powMod()

Performs modular exponentiation.


    public
                powMod(BigInteger $e, BigInteger $n) : BigInteger

Alias for modPow().

Parameters

$e : BigInteger
$n : BigInteger

Return values

BigInteger —

setPrecision()

Set Precision


    public
                setPrecision(int $bits) : mixed

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

Parameters

$bits : int

Return values

mixed —