Math_BigInteger

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: toString(); // outputs 50 ?>

PHP4 compatible Default Constructor.

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: toBytes(); // outputs chr(65) ?>

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: toHex(); // outputs '41' ?>

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: toBits(); // outputs '1000001' ?>

Converts a BigInteger to a base-10 number.

Here's an example: toString(); // outputs 50 ?>

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}

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

__sleep() magic method

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

__wakeup() magic method

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

__debugInfo() magic method

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

Adds two BigIntegers.

Here's an example: add($b); echo $c->toString(); // outputs 30 ?>

Performs addition.

Subtracts two BigIntegers.

Here's an example: subtract($b); echo $c->toString(); // outputs -10 ?>

Performs subtraction.

Multiplies two BigIntegers

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

Performs multiplication.

Performs long multiplication on two BigIntegers

Modeled after 'multiply' in MutableBigInteger.java.

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

Performs squaring

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.

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

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: divide($b); echo $quotient->toString(); // outputs 0 echo "\r\n"; echo $remainder->toString(); // outputs 10 ?>

Divides a BigInteger by a regular integer

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

Performs modular exponentiation.

Here's an example: modPow($b, $c); echo $c->toString(); // outputs 10 ?>

Performs modular exponentiation.

Alias for Math_BigInteger::modPow()

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.

Modular reduction

For most $modes this will return the remainder.

Modular reduction preperation

Modular multiply

Modular square

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.

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.

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

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.

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.

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}

Prepare a number for use in Montgomery Modular Reductions

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!

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

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 693x + 609y == 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: extendedGCD($b)); echo $gcd->toString() . "\r\n"; // outputs 21 echo $a->toString() * $x->toString() + $b->toString() * $y->toString(); // outputs 21 ?>

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

Absolute value.

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

Compares two numbers.

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

Set Precision

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

Logical And

Logical Or

Logical Exclusive-Or

Logical Not

Logical Right Shift

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

Logical Left Shift

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

Logical Left Rotate

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

Logical Right Rotate

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

Set random number generator function

This function is deprecated.

Generates a random BigInteger

Byte length is equal to $length. Uses crypt_random if it's loaded and mt_rand if it's not.

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)

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.

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.

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. Math_BigInteger::randomPrime() can be distributed across multiple pageloads on a website instead of just one.

Logical Left Shift

Shifts BigInteger's by $shift bits.

Logical Right Shift

Shifts BigInteger's by $shift bits.

Normalize

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

Trim

Removes leading zeros

Array Repeat

Logical Left Shift

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

Logical Right Shift

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

Converts 32-bit integers to bytes.

Converts bytes to 32-bit integers

DER-encode an integer

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

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.